原题链接在这里：https://leetcode.com/problems/trapping-rain-water/
参考这篇帖子：http://www.cnblogs.com/springfor/p/3877101.html
那么如何求A[i]的左右高度呢？ 要知道，能盛多少水主要看短板。那么对每个A[i]来说，要求一个最高的左短板，再求一个最高的右短板，这两个直接最短的板子减去A[i]原有的值就是能成多少水了。
所以需要两遍遍历，一个从左到右，找最高的左短板；一个从右到左，找最高的右短板。最后记录下盛水量的总值就是最终结果了。
AC Java:
1 public class Solution { 2 public int trap(int[] height) { 3 if(height == null || height.length == 0){ 4 return 0; 5 } 6 int [] leftBar = new int[height.length]; 7 int [] rightBar = new int[height.length]; 8 9 //From left to right, calculate highest bar on the left including itself 10 int max = 0; 11 for(int i = 0; i<height.length; i++){ 12 max = Math.max(max,height[i]); 13 leftBar[i] = max; 14 } 15 //Form right to left, calculate highest bar on the right including itself 16 max = 0; 17 for(int i = height.length-1; i>=0; i--){ 18 max = Math.max(max,height[i]); 19 rightBar[i] = max; 20 } 21 22 int res = 0; 23 for(int i = 0; i<height.length; i++){ 24 res += (Math.min(leftBar[i],rightBar[i])-height[i]) * 1; 25 } 26 return res; 27 } 28 }
对照着代码再看原来的例子：
index: 0 1 2 3 4 5 6 7 8 9 10 11
A[index]: 0 1 0 2 1 0 1 3 2 1 2 1
left[index]: 0 1 1 2 2 2 2 3 3 3 3 3
right[index]: 3 3 3 3 3 3 3 3 2 2 2 1
min[i]: 0 1 1 2 2 2 2 3 2 2 2 1
bit[i]: - 0 1 0 1 2 1 0 0 1 0 0
那么根据上表可以算出最终结果是6。
原文：http://www.cnblogs.com/Dylan-Java-NYC/p/4881254.html