Trapping Rain Water
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.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
分析：
leftMaxHeight:表示当前柱子左面柱子的最高高度
rightMaxHeight:表示当前柱子右面柱子的最高高度
则当前柱子能够容纳的水与height[i]与leftMaxHeight和rightMaxHeight有关。
代码如下:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int trap(int[] height) {
if (height == null || height.length < 3) {
return 0;
}
int result = 0;
int[] left = new int[height.length];
int[] right = new int[height.length];
left[0] = height[0];
right[height.length - 1] = height[height.length - 1];
for (int i = 1; i < height.length; i++) {
left[i] = Math.max(left[i - 1], height[i]);
right[height.length - i - 1] = Math.max(right[height.length - i], height[height.length - i - 1]);
}
// 再次遍历height[]，取它左右最大高度的最小值，减去height[i]，就是它的积水量。累加所有挡板的积水量。
for (int i = 1; i < height.length - 1; i++) {
result += Math.min(left[i], right[i]) - height[i];
}
return result;
}
}
近期评论