42. 接雨水 #
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
提示：
n == height.length1 <= n <= 2 * 1040 <= height[i] <= 105
解答 #
1 动态规划 #
class Solution {
public int trap(int[] height) {
int len=height.length;
int[] toRight=new int[len];
int[] toLeft=new int[len];
for(int i=1;i<len;i++){
toRight[i]=Math.max(toRight[i-1],height[i-1]);
toLeft[len-i-1]=Math.max(toLeft[len-i],height[len-i]);
}
// System.out.println(Arrays.toString(toRight));
// System.out.println(Arrays.toString(toLeft));
// System.out.println(Arrays.toString(height));
int sum=0;
for(int i=1;i<len-1;i++){
if(height[i]<Math.min(toRight[i],toLeft[i]))
sum+=Math.min(toRight[i],toLeft[i])-height[i];
}
return sum;
}
}
复杂度分析
- 时间复杂度：O(n)，其中 n 是数组 height 的长度。计算数组 leftMax 和 rightMax 的元素值各需要遍历数组 height 一次，计算能接的雨水总量还需要遍历一次。
- 空间复杂度：O(n)，其中 n 是数组 height 的长度。需要创建两个长度为 n 的数组 leftMax 和 rightMax。
2 单调栈 #
- 当遍历到下标i时：
- 如果栈内至少有两个元素，栈顶元素为top，栈顶的下面一个元素是left，则一定有height[left] >= height[top]。
- 如果height[i] > height[top]，则得到一个可以接雨水的区域，该区域的宽度是i - left - 1，高度是min(height[left], height[i]) - height[top]。
- 根据宽度和高度，即可计算得到该区域能接的雨水量。
- 例如：
- 宽度：i - left - 1
- 高度：min(height[left], height[i]) - height[top]
- 为了得到left，需要将top出栈。在对top计算能接的雨水量之后，left 变成新的 top。重复上述操作，直到栈变为空，或者栈顶下表对应的height中的元素大于或等于height[i]。
- 在对下标i处计算能接的雨水量之后，将i入栈，继续遍历后面的下表，计算能接的雨水量。
- 遍历结束后即可得到能接的雨水总量。
class Solution {
public int trap(int[] height) {
int len=height.length;
//实现一个单调递减的栈，栈里面的值存放下标
Deque<Integer> sk=new ArrayDeque<>();
int sum=0;
for(int i=0;i<len;i++){
while(!sk.isEmpty()&&height[sk.peek()]<height[i]){
int top=sk.pop();
if(sk.isEmpty()){
break;
}
int left=sk.peek();
sum+=(i-left-1)*(Math.min(height[i],height[left])-height[top]);
}
sk.push(i);
}
return sum;
}
}
复杂度分析
- 时间复杂度：O(n)，其中 n 是数组 height 的长度。从 0 到 n−1 的每个下标最多只会入栈和出栈各一次。
- 空间复杂度：O(n)，其中 n 是数组 height 的长度。空间复杂度主要取决于栈空间，栈的大小不会超过 n。
3 双指针 #
class Solution {
public int trap(int[] height) {
int len = height.length;
int sum = 0;
int left = 0;
int right = len - 1;
int leftMax = height[left];
int rightMax = height[right];
while (left < right) {
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
if (height[left] < height[right]) {
sum += leftMax - height[left];
left++;
} else {
sum += rightMax - height[right];
right--;
}
}
return sum;
}
}
复杂度分析
- 时间复杂度：O(n)，其中 n 是数组 height 的长度。两个指针的移动总次数不超过 n。
- 空间复杂度：O(1)。只需要使用常数的额外空间。
动态规划的做法中，需要维护两个数组 leftMax 和 rightMax，因此空间复杂度是 O(n)。是否可以将空间复杂度降到 O(1)？
注意到下标 i 处能接的雨水量由 leftMax[i] 和 rightMax[i] 中的最小值决定。由于数组 leftMax 是从左往右计算，数组 rightMax 是从右往左计算，因此可以使用双指针和两个变量代替两个数组。
维护两个指针 left 和 right，以及两个变量 leftMax 和 rightMax，初始时 left=0,right=n−1,leftMax=0,rightMax=0。指针 left 只会向右移动，指针 right 只会向左移动，在移动指针的过程中维护两个变量 leftMax 和 rightMax 的值。
当两个指针没有相遇时，进行如下操作：
- 使用 height[left] 和 height[right] 的值更新 leftMax 和 rightMax 的值；
- 如果 height[left]<height[right]，则必有 leftMax<rightMax，下标 left 处能接的雨水量等于 leftMax−height[left]，将下标 left 处能接的雨水量加到能接的雨水总量，然后将 left 加 1（即向右移动一位）；
- 如果 height[left]≥height[right]，则必有 leftMax≥rightMax，下标 right 处能接的雨水量等于 rightMax−height[right]，将下标 right 处能接的雨水量加到能接的雨水总量，然后将 right 减 1（即向左移动一位）。
当两个指针相遇时，即可得到能接的雨水总量。
方法三如果 height[left] < height[right]，则必有 leftMax < rightMax可以这么理解： 注意代码中左右指针缩进的规则如下， if (height[left] < height[right]) { left++; } else { right--; } ，在这个规则移动下的左右指针，left和right必定有一个是指向当前已扫描过的区域的最大值的，假设比较得到height[left]<height[right]，说明left指针不会是最大值，那么right指针必为最大值，其为rightMax，同时也大于leftMax