题目：
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], return6.
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!
分析：
给定一个数组，每个数代表该位置上的长条的高度，由此得到一个类似地形图的东西。凹进去的地方可以蓄水，问一共能存多少水。
每一个坑（凹进去的地方）都是由左右2个长条围成的。能存多少水取决于这2个长条中最短的那个。因此，我们对数组进行2次遍历。第1次从左向右，获得该位置左侧最高长条的高度；第2次从右向左，获得该位置右侧最高长条的高度。现在每个位置都知道了它所在的坑被围成的左右2个长条的高度，取较短的那个，就是该位置蓄水的最大高度。最后把每个位置的蓄水量加起来即可。
代码：
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
public class Solution { public int trap(int[] height) { int res = 0; int len = height.length; if(len == 0) return 0; int[] left = new int[len]; left[0] = 0; for(int i = 1; i < len; i++){ left[i] = Math.max(left[i-1], height[i-1]); } int right = 0; for(int i = len - 1; i >= 0; i--){ int top = Math.min(left[i], right); res += Math.max(top - height[i], 0); right = Math.max(right, height[i]); } return res; } } |