题目描述
给定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
分析
题目容易被所给的图带偏，其实给出简单的xy坐标图，就很容易想到解法。
关键是理解能存水的是单向递增（递减）的节点，存水的数量是任意两个递增（递减）节点间的数值小的节点所决定，公式为：（小节点值-区间内节点值）。
思路是从左往右，找递增节点，算出可存水数量，再从右往左找递增，但这时已经知道最大值节点（从左往右时得到），所以不用遍历整个数组，到最大值就可以结束。
代码
class Solution {
public int trap(int[] height) {
if(height.length == 0)
return 0;
int water = 0;
int maxIndex = 0;
int max = height[maxIndex];
for (int i = 1; i < height.length; i++) {
int cur = height[i];
if (cur >= max) {
if (maxIndex > -1) {
for (int j = maxIndex + 1; j < i; j++) {
water += max - height[j];
}
}
maxIndex = i;
max = cur;
}
}
int end = maxIndex;
maxIndex = height.length - 1;
max = height[maxIndex];
for (int i = height.length - 2; i >= end; i--) {
int cur = height[i];
if (cur >= max) {
if (maxIndex > -1) {
for (int j = maxIndex - 1; j > i; j--) {
water += max - height[j];
}
}
maxIndex = i;
max = cur;
}
}
return water;
}
}
