42. 接雨水
思路：
可以使用双指针法也可以使用单调栈。
双指针方法纵向求解：
在纵向求解中，我们将问题简化为在每个柱子的位置上能够存储多少水。使用双指针法时，我们分别从数组的两端向中间移动，维护两个指针和两个变量（左侧最大高度和右侧最大高度）。这种方法侧重于通过比较当前位置柱子的高度和其两侧最大高度的较小值来计算当前位置能够存储的水量。
左右指针移动：从数组两端开始，通过比较左右指针当前位置的高度来决定移动哪个指针。
更新最大高度：每次移动指针时，更新左侧和右侧的最大高度。
计算水量：根据当前位置的高度和左右最大高度的较小值，计算出当前位置能够存储的水量，并累加到总水量中。
单调栈横向求解：
在横向求解中，我们考虑的是在每一层高度上能够存储多少水。使用单调栈时，我们维护一个单调递减的栈，栈中存放的是数组中柱子的索引。这种方法侧重于处理每一层高度上的凹槽，通过维护一个栈来记录形成凹槽的柱子。
单调递减栈：栈中存放的是数组中柱子的索引，保证栈顶到栈底对应的柱子高度是递减的。
计算水量：遍历数组中的每个柱子，如果当前柱子的高度大于栈顶柱子的高度，则说明形成了一个凹槽，可以计算该凹槽能接的雨水量。根据当前柱子和栈顶柱子的高度，计算凹槽的宽度和高度，从而得到能够存储的水量，并累加到总水量中。
题解：
public int trap(int[] height) {
// 方法一：使用两个额外的数组存储每个位置的左右最大高度，然后计算每个位置能接的雨水量
int n = height.length;
int[] pre = new int[n];
pre[0] = height[0];
int[] suf = new int[n];
suf[n - 1] = height[n - 1];
// 计算每个位置左边的最大高度
for (int i = 1; i < height.length; i++) {
pre[i] = Math.max(pre[i - 1], height[i]);
}
// 计算每个位置右边的最大高度
for (int i = height.length - 2; i >= 0; i--) {
suf[i] = Math.max(height[i], suf[i + 1]);
}
int sum = 0;
// 计算每个位置能接的雨水量并累加
for (int i = 0; i < pre.length; i++) {
sum += Math.min(pre[i], suf[i]) - height[i];
}
return sum;
}
public int trap2(int[] height) {
// 方法二：双指针法，使用两个指针从两端向中间扫描，维护左右最大高度，并计算能接的雨水量
int n = height.length;
int preMax = height[0];
int sufMax = height[n - 1];
int sum = 0;
for (int i = 0, j = n - 1; i < j; ) {
// 更新左右最大高度
preMax = Math.max(preMax, height[i]);
sufMax = Math.max(sufMax, height[j]);
// 计算当前位置能接的雨水量并累加
sum += preMax < sufMax ? preMax - height[i++] : sufMax - height[j--];
}
return sum;
}
public int trap3(int[] height) {
// 方法三：单调栈法，使用单调递减栈来处理，计算每个位置能接的雨水量并累加
int sum = 0; // 总雨水量初始化为0
Deque<Integer> stack = new LinkedList<>(); // 创建一个单调递减栈，栈中存储的是数组的索引
for (int i = 0; i < height.length; i++) {
// 当前位置的高度大于栈顶索引对应的高度时，说明形成了凹槽可以接雨水
while (!stack.isEmpty() && height[i] > height[stack.peekLast()]) {
int mid = stack.pollLast(); // 弹出栈顶元素，即凹槽的底部
if (!stack.isEmpty()) {
int left = stack.peekLast(); // 获取新的栈顶元素，即凹槽的左边界
// 这个i可以看作右边界
int h = Math.min(height[left], height[i]) - height[mid]; // 计算凹槽的高度
int w = i - left - 1; // 计算凹槽的宽度
sum += h * w; // 累加当前凹槽能接的雨水量
}
}
stack.addLast(i); // 当前位置入栈
}
return sum; // 返回总的雨水量
}
84.柱状图中最大的矩形
题目链接：84.柱状图中最大的矩形
文档讲解：代码随想录
状态：不会
思路：
遍历每个柱子（包括一个额外的结束标志）：
- 如果当前柱子的高度大于栈顶柱子的高度，将当前柱子的索引入栈。
- 如果当前柱子的高度小于等于栈顶柱子的高度，说明栈顶柱子找到了右边界，可以计算栈顶柱子作为高度的最大矩形面积了。
- 弹出栈顶元素，计算以该柱子高度为高的矩形的面积，宽度为当前柱子索引与新的栈顶元素索引之差减一（因为不包括栈顶元素本身）。
- 更新最大面积。
- 最后，处理完所有柱子后，栈中剩余的柱子形成的矩形面积也需要计算，因为它们没有右边界，宽度可以看作是数组的长度。
- 在遍历完所有柱子后，添加一个高度为 0 的结束标志，确保栈中剩余的柱子也能得到处理。
题解：
public int largestRectangleArea(int[] heights) {
int area = 0;
Deque<Integer> stack = new LinkedList<>();
for (int i = 0; i <= heights.length; i++) {
// 处理 heights 数组的最后一个元素后，我们需要一个结束标志来处理栈中剩余的元素。
// 具体来说，当 i 等于 heights.length 时，表示我们已经遍历完了数组的所有元素，此时将 h 设置为 0 是为了触发栈中剩余元素的处理。
int h = (i == heights.length) ? 0 : heights[i];
while (!stack.isEmpty() && h < heights[stack.peekLast()]) {
// 栈顶元素是栈内最大的值是height,弹出后第二大元素就是heights[stack.peekLast()]
// 利用栈内第二大元素的下标得到width
int height = heights[stack.pollLast()];
// 栈顶元素到第二大元素之间的宽度
int width = stack.isEmpty() ? i : i - stack.peekLast() - 1;
area = Math.max(area, height * width);
}
stack.addLast(i);
}
return area;
}
