Description
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
water
Example:
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Solution
DP, time O(n), space O(n)
某个位置 i 能够存储的水 = min(i 左边的最高height, i 右边的最高height) - height[i]
注意存储的水量不能为负，最低是0.
class Solution {
public int trap(int[] height) {
if (height == null || height.length < 3) {
return 0;
}
int n = height.length;
int[] maxLeft = new int[n];
maxLeft[0] = height[0];
for (int i = 1; i < n - 1; ++i) {
maxLeft[i] = Math.max(height[i], maxLeft[i - 1]);
}
int max = height[n - 1];
int total = 0;
for (int i = n - 2; i > 0; --i) {
max = Math.max(height[i], max);
total += Math.min(maxLeft[i], max) - height[i];
}
return total;
}
}
上面的maxLeft[i]是包含height[i]的，可能有点描述不清，向下面这样写也是极好的，maxLeft[i]就是i左边最高的值，maxRight是i右边最高的值，计算trapped的时候要注意水量最少是0，不能为负值。
class Solution {
public int trap(int[] height) {
if (height == null || height.length < 3) {
return 0;
}
int n = height.length;
int[] maxLeft = new int[n];
for (int i = 1; i < n - 1; ++i) {
maxLeft[i] = Math.max(height[i - 1], maxLeft[i - 1]);
}
int maxRight = 0;
int total = 0;
for (int i = n - 2; i > 0; --i) {
maxRight = Math.max(height[i + 1], maxRight);
total += Math.max(Math.min(maxLeft[i], maxRight) - height[i], 0);
}
return total;
}
}
