来源Leetcode第42题接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
示例:
1
2
| 输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
|
找短板
对每一个要求的位置，寻找左右两边最高的列，然后取较小的，如果较小列大于当前列，就可以装水。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public int trap(int[] height) {
if(height.length == 0)
return 0;
int sum = 0;
for(int i = 1 ; i < height.length - 1 ; i++){
int left_max = 0,right_max = 0;
for(int j = i - 1; j >= 0; j--)
left_max = Math.max(left_max,height[j]);
for(int j = i + 1; j < height.length; j++)
right_max = Math.max(right_max,height[j]);
int min = Math.min(left_max,right_max);
if(min > height[i])
sum += min - height[i];
}
return sum;
}
|
动态规划
来源
对于每一列，我们求它左边最高的墙和右边最高的墙，都是重新遍历一遍所有高度，这里我们可以优化一下。
首先用两个数组，max_left [i]代表第 i 列左边最高的墙的高度，max_right[i] 代表第 i 列右边最高的墙的高度。（一定要注意下，第 i 列左（右）边最高的墙，是不包括自身的，和 leetcode 上边的讲的有些不同）
对于 max_left我们其实可以这样求。
max_left [i] = Max(max_left [i-1],height[i-1])。它前边的墙的左边的最高高度和它前边的墙的高度选一个较大的，就是当前列左边最高的墙了。
对于 max_right我们可以这样求。
max_right[i] = Max(max_right[i+1],height[i+1]) 。它后边的墙的右边的最高高度和它后边的墙的高度选一个较大的，就是当前列右边最高的墙了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public int trap(int[] height) {
int sum = 0;
int[] max_left = new int[height.length];
int[] max_right = new int[height.length];
for (int i = 1; i < height.length - 1; i++) {
max_left[i] = Math.max(max_left[i - 1], height[i - 1]);
}
for (int i = height.length - 2; i >= 0; i--) {
max_right[i] = Math.max(max_right[i + 1], height[i + 1]);
}
for (int i = 1; i < height.length - 1; i++) {
int min = Math.min(max_left[i], max_right[i]);
if (min > height[i]) {
sum = sum + (min - height[i]);
}
}
return sum;
}
|
双指针
来源
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
| public int trap(int[] height) {
int sum = 0;
int max_left = 0;
int max_right = 0;
int left = 1;
int right = height.length - 2;
for (int i = 1; i < height.length - 1; i++) {
if (height[left - 1] < height[right + 1]) {
max_left = Math.max(max_left, height[left - 1]);
int min = max_left;
if (min > height[left]) {
sum = sum + (min - height[left]);
}
left++;
} else {
max_right = Math.max(max_right, height[right + 1]);
int min = max_right;
if (min > height[right]) {
sum = sum + (min - height[right]);
}
right--;
}
}
return sum;
}
|
单调栈
当遍历墙的高度的时候，如果当前高度小于栈顶的墙高度，说明这里会有积水，我们将墙的高度的下标入栈。
如果当前高度大于栈顶的墙的高度，说明之前的积水到这里停下，我们可以计算下有多少积水了。计算完，就把当前的墙继续入栈，作为新的积水的墙。
总体的原则就是，
- 当前高度小于等于栈顶高度，入栈，指针后移。
- 当前高度大于栈顶高度，出栈，计算出当前墙和栈顶的墙之间水的多少，然后计算当前的高度和新栈的高度的关系，重复第 2 步。直到当前墙的高度不大于栈顶高度或者栈空，然后把当前墙入栈，指针后移。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public int trap(int[] height) {
if(height.length == 0)
return 0;
Stack<Integer> stack = new Stack<>();
int ans = 0;
int popIndex;
for(int i = 0 ; i < height.length ; ++i){
while (!stack.isEmpty() && height[stack.peek()] < height[i]){
popIndex = stack.pop();
while (!stack.isEmpty() && height[stack.peek()] == height[popIndex])
stack.pop();
if(!stack.isEmpty()){
int peekIndex = stack.peek();
ans += (Math.min(height[stack.peek()],height[i]) - height[popIndex]) * (i - peekIndex - 1);
}
}
stack.push(i);
}
return ans;
}
|