题目
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
分析
1.自己一开始的想法：把上图分为一层一层，每一层的高度为1,用栈分别计算每层的凹进去格子个数，加在一起，哈哈哈哈哈，数据量小还可以用，数据量一大，就超时了，时间复杂度O(n^2)。
2.还是看了解题报告，只要遍历三次，就可以得出结果，哇塞好神奇。
其实这个题只要能知道第x个柱子的 左边最高柱子 和 右边最高柱子 中比较矮的一个，然后用较矮柱子的高度减去当前第x个柱子的高度，就是当前x柱子可以接住的雨水量。
说的有点儿绕，写成表达式就是： x柱子接住雨水量 = min( left_max, right_max) - height[x]
代码
class Solution {
public int trap(int[] height) {
int len = height.length;
if (len == 0) return 0;
int[] left_max = new int[len];
int[] right_max = new int[len];
int max = height[0];
for (int i = 0; i < len; i++) {
if (max > height[i]){
left_max[i] = max;
}else{
left_max[i] = height[i];
max = height[i];
}
}
max = height[len-1];
for (int i = len-2; i >= 0; i--) {
if (max > height[i]){
right_max[i] = max;
}else{
right_max[i] = height[i];
max = height[i];
}
}
int sum = 0;
for (int i = 1; i < len-1; i++) {
sum += Math.min(left_max[i],right_max[i]) - height[i];
}
return sum;
}
}
| 
转播
