第10章单调栈-part02，面试高频题接雨水拿下。
42. 接雨水
1.1 解题分析
本题是接雨水，要同时求当前柱子左边第一个比自己的高的、以及右边第一个比自己高的柱子，直观的就是暴力解法，O(n^2)时间复杂度，第一个for循环遍历数组，第二个for循环开始找左边比自己高的、右边比自己高的。由此还有双指针优化，预处理。
而单调栈解法，如图模拟：
- 栈中仍然存储的是数组的下标，遍历过程中，当前遍历元素和栈顶元素有三种判断情况。
- 找凹槽不像暴力解法是按列计算的，单调栈是按行横向的面积计算，体会一下。
- 左边第一个比栈顶元素高的柱子很自然就存在栈中，掌握这一点题目就解决了。
- 关于两个柱子高度一样时，存入栈最后面积计算会是0，先弹出再存入的做法可以减少冗余计算。
1.2 解题小结
接雨水暴力解法的核心逻辑是：
对于当前列i，能接住的雨水体积 = min(左侧最大高度, 右侧最大高度) - 当前柱子高度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public int trap(int[] height) {
int res = 0;
for (int i = 0; i < height.length; i++) {
if (i == 0 || i == height.length - 1) continue;
int lHeight = height[i];
int rHeight = height[i];
for (int j = i + 1; j < height.length; j++) {
rHeight = Math.max(rHeight, height[j]);
}
for (int j = i - 1; j >= 0; j--) {
lHeight = Math.max(lHeight, height[j]);
}
int h = Math.min(lHeight, rHeight) - height[i];
res += h * 1;
}
return res;
}
|
- 双指针优化
把每一个位置的左边最高高度记录在一个数组上（maxLeft），右边最高高度记录在一个数组上（maxRight），避免每到一个柱子都向两边遍历一遍，重复计算。
当前位置，左边的最高高度是前一个位置的左边最高高度和本高度的最大值。
即从左向右遍历：maxLeft[i] = max(height[i], maxLeft[i - 1]);
从右向左遍历：maxRight[i] = max(height[i], maxRight[i + 1]);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int trap(int[] height) {
int res = 0;
int n = height.length;
int[] maxLeft = new int[n];
int[] maxRight = new int[n];
maxLeft[0] = height[0];
for (int i = 1; i < n; i++) {
maxLeft[i] = Math.max(height[i], maxLeft[i - 1]);
}
maxRight[n - 1] = height[n - 1];
for (int j = n - 2; j >= 0; j--) {
maxRight[j] = Math.max(height[j], maxRight[j + 1]);
}
for (int i = 0; i < n; i++) {
if (i == 0 || i == n - 1) continue;
int h = Math.min(maxLeft[i], maxRight[i]) - height[i];
res += h;
}
return res;
}
}
|
- 第一遍写题时，计算雨水高度时没有减去凹槽底部的高度，导致计算错误。
- 单调栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public int trap(int[] height) {
int res = 0;
Deque<Integer> stack = new ArrayDeque<>();
stack.offerFirst(0);
for (int i = 1; i < height.length; i++) {
if (!stack.isEmpty() && height[i] < height[stack.peekFirst()]) {
stack.offerFirst(i);
} else if (!stack.isEmpty() && height[i] == height[stack.peekFirst()]){
stack.pollFirst();
stack.offerFirst(i);
} else {
while (!stack.isEmpty() && height[i] > height[stack.peekFirst()]) {
Integer midIndex = stack.pollFirst();
if (!stack.isEmpty()) {
int h = Math.min(height[i], height[stack.peekFirst()]) - height[midIndex];
int w = i - stack.peekFirst() - 1;
res += h * w;
}
}
stack.offerFirst(i);
}
}
return res;
}
}
|
84.柱状图中最大的矩形
2.1 解题分析
本题与42. 接雨水遥相呼应，一个是求自己左右两边比自己高的柱子高度，而本题是求比自己矮的柱子高度，同样需要3个元素参与计算体积，非常类似。
最大的区别是，为了防止柱子本身就是单调递减的（无法触发收获结果的条件），或者柱子是单调递增的（此时不满足有3个元素），我们需要在数组的首尾分别加一个0。
2.2 解题小结
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public int largestRectangleArea(int[] heights) {
int res = 0;
int[] newHeights = new int[heights.length + 2];
newHeights[0] = 0;
newHeights[heights.length + 1] = 0;
System.arraycopy(heights, 0, newHeights, 1, heights.length);
heights = newHeights;
Deque<Integer> stack = new ArrayDeque<>();
stack.offerFirst(0);
for (int i = 1; i < heights.length; i++) {
if (!stack.isEmpty() && heights[i] >= heights[stack.peekFirst()]) {
stack.offerFirst(i);
} else {
while (!stack.isEmpty() && heights[i] < heights[stack.peekFirst()]) {
Integer midIdx = stack.pollFirst();
if (!stack.isEmpty()) {
int h = heights[midIdx];
int w = i - stack.peekFirst() - 1;
res = Math.max(res, h * w);
}
}
stack.offerFirst(i);
}
}
return res;
}
}
|
3. 今日收获
- JAVA的数组扩容只能新建一个新数组哦，不过建好之后索引可以再指向这个新数组，更舒服一点。
- 学习时长：2小时