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.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
Thanks Marcos
思路：
用两个数组，leftMax[i]表示左边到i-1为之最高的高度，rightMax同上。
某位置能存储的水量等于min{leftMax[i],rightMax[i]}-height[i]
算法：
public int trap(int[] height) {
int water = 0;
int left_max[] = new int[height.length];
int right_max[] = new int[height.length];
for (int j = 1; j < height.length - 1; j++) {
left_max[j] = Math.max(left_max[j - 1], height[j - 1]);
}
for (int j = height.length - 2; j >=0; j--) {
right_max[j] = Math.max(right_max[j + 1], height[j + 1]);
}
for (int i = 1; i < height.length - 1; i++) {
int tmp = Math.min(left_max[i], right_max[i]) - height[i];
if (tmp > 0)
water += tmp;
}
return water;
}