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.
这个题的思路应该是，根据当前bar的左右两侧的最高的bar的高度，可以计算出当前bar可以储存的水。
所以用三个循环。第一个从左到右扫描，保存下每个bar左侧最高bar的高度。
第二个从右到左，保存下每个bar右侧最高bar的高度。
最后通过前两个计算出每个bar可以存水多少，加和。
1 public int trap(int[] A) { 2 if (A.length == 0) return 0; 3 int[] left = new int[A.length]; 4 int[] right = new int[A.length]; 5 6 int max = A[0]; 7 for (int i=0; i<A.length; i++) { 8 if (A[i] > max) { 9 max = A[i]; 10 } 11 left[i] = max; 12 } 13 max = A[A.length-1]; 14 for (int i=A.length-1; i>=0; i--) { 15 if (A[i] > max) { 16 max = A[i]; 17 } 18 right[i] = max; 19 } 20 int total = 0; 21 for (int i=0; i<A.length; i++) { 22 int t = Math.min(left[i], right[i]); 23 total += t > A[i] ? t-A[i] : 0; 24 } 25 26 return total; 27 }
LeetCode: Trapping Rain Water,布布扣,bubuko.com
原文：http://www.cnblogs.com/longhorn/p/3593474.html