Leetcode题解（3）：接雨水
1. 动态规划
对于任意一个条形块 $height[i]$ ，能蓄水的必要条件是存在 $i > l > 0$ ，$i< r < n$ 使得 $height[l] > height[i]$ 并且 $height[r] > height[i]$ 。当上述条件成立时，这个条形块的蓄水量就等于 $min(height[l],\ height[r]) - height[i]$ 。所以我们可以记录每个条形块对应的左右两边最高的条形块，然后每次遍历时比较左右两边的最高条形块，并取其中较小者。
class Solution {
public int trap(int[] height) {
int n = height.length;
if (n == 0) return 0;
int[] left = new int[n];
int[] right = new int[n];
left[0] = height[0];
right[n - 1] = height[n - 1];
for (int i = 1; i < n; i++)
left[i] = Integer.max(height[i], left[i - 1]);
for (int i = n - 2; i >= 0; i--)
right[i] = Integer.max(height[i], right[i + 1]);
int res = 0;
for (int i = 1; i < n - 1; i++)
res += (Integer.min(left[i], right[i])) - height[i];
return res;
}
}
2. 双指针
观察上面的 $left[\ ]$ 和 $right[\ ]$ ，可以发现它们元素的状态仅依赖于其左边或者右边元素的状态以及 $height[\ ]$ ，我们可以利用这个特性，将数组优化掉。
对于每个 $i$ ，只要 $left[i] > height[i]$ ，$right[i] > height[i]$ ，并且 $left[i] < right[i]$ ，那么就由左边条形柱决定蓄水量，否则就由右边决定。也就是说，对于每个 $height[i]$ ，只要其左右两边存在 $left_-max > height[i]$ 并且 $right_-max > height[i]$ 即可蓄水。所以我们可以记录一个 $left_-max$ 和一个 $right_-max$ ，然后利用双指针遍历更新。指针移动规则是：
- 如果 $height[l] < height[r]$ ，则移动左指针；
- 否则，移动右指针。
采用上述的更新规则后，左右指针中的一个会最终指向最高的条形柱并固定不动。代码实现如下：
class Solution {
public int trap(int[] height) {
int l = 0, r = height.length - 1, res = 0, left_max = 0, right_max = 0;
while (l <= r) {
if (height[l] < height[r]) {
if (height[l] > left_max) left_max = height[l];
else res += left_max - height[l];
l++;
} else {
if (height[r] > right_max) right_max = height[r];
else res += right_max - height[r];
r--;
}
}
return res;
}
}