题目
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.
答案
maintain i左边最高的bar x，i右边最高的bar y
i位置上有多少水取决于x和y短的那一节
用x或y减去当前i的bar，就知道i能有多少水
class Solution {
// e.g input: 2 0 2
public int trap(int[] height) {
int left = 0, right = height.length - 1, n = height.length;
int[] leftmax = new int[n], rightmax = new int[n];
int area = 0;
// Generate leftmax (leftmax[0] = 0)
for(int i = 1; i < n; i++) {
leftmax[i] = Math.max(leftmax[i - 1], height[i - 1]);
}
// Generate rightmax
for(int i = n - 2; i >= 0; i--) {
rightmax[i] = Math.max(rightmax[i + 1], height[i + 1]);
}
// left max: 0 2 2
// right max: 2 2 0
for(int i = 0; i < n; i++) {
int water_level = Math.min(leftmax[i], rightmax[i]);
if(height[i] >= water_level) continue;
else area += (water_level - height[i]);
}
return area;
}
}
