<困难> 接雨水
来源：LeetCode.
给定 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 = = h e i g h t . l e n g t h n == height.length n==height.length
- 1 < = n < = 2 ∗ 104 1 <= n <= 2 * 104 1<=n<=2∗104
- 0 < = h e i g h t [ i ] < = 105 0 <= height[i] <= 105 0<=height[i]<=105
接下来看一下解题思路：
思路一：双指针：下标 i i i 处能接的雨水量由 leftMax [ i ] textit{leftMax}[i] leftMax[i] 和 rightMax [ i ] textit{rightMax}[i] rightMax[i] 中的最小值决定。由于数组 leftMax textit{leftMax} leftMax 是从左往右计算，数组 rightMax textit{rightMax} rightMax 是从右往左计算，因此可以使用双指针。
维护两个指针 left textit{left} left 和 right textit{right} right，以及两个变量 leftMax textit{leftMax} leftMax 和 rightMax textit{rightMax} rightMax，初始时 left = 0 , right = n − 1 , leftMax = 0 , rightMax = 0 textit{left}=0,textit{right}=n-1,textit{leftMax}=0,textit{rightMax}=0 left=0,right=n−1,leftMax=0,rightMax=0。指针 left textit{left} left 只会向右移动，指针 right textit{right} right 只会向左移动，在移动指针的过程中维护两个变量 leftMax textit{leftMax} leftMax 和 rightMax textit{rightMax} rightMax 的值。
当两个指针没有相遇时，进行如下操作：
-
使用 height [ left ] textit{height}[textit{left}] height[left] 和 height [ right ] textit{height}[textit{right}] height[right] 的值更新 leftMax textit{leftMax} leftMax 和 rightMax textit{rightMax} rightMax 的值；
-
如果 height [ left ] < height [ right ] textit{height}[textit{left}]
-
如果 height [ left ] ≥ height [ right ] textit{height}[textit{left}] ge textit{height}[textit{right}] height[left]≥height[right]，则必有 leftMax ≥ rightMax textit{leftMax} ge textit{rightMax} leftMax≥rightMax，下标 right textit{right} right 处能接的雨水量等于 rightMax − height [ right ] textit{rightMax}-textit{height}[textit{right}] rightMax−height[right]，将下标 right textit{right} right 处能接的雨水量加到能接的雨水总量，然后将 right textit{right} right 减 1 1 1（即向左移动一位）。
当两个指针相遇时，即可得到能接的雨水总量。
class Solution {
public int trap(int[] height) {
int n = height.length;
if (n < 3) {
return 0;
}
int left = 0;
int right = n - 1;
int leftMax = 0;
int rightMax = 0;
int res = 0;
while (left < right){
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
if (leftMax < rightMax) {
res += (leftMax - height[left]);
++left;
} else {
res += (rightMax - height[right]);
--right;
}
}
return res;
}
}
复杂度分析
- 时间复杂度： O ( n ) O(n) O(n)，其中 n n n 是数组 height textit{height} height 的长度。两个指针的移动总次数不超过 n n n。
- 空间复杂度： O ( 1 ) O(1) O(1)。只需要使用常数的额外空间。
