给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
image.png
上面是由数组 [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
解
首先找到数组中的最大值，然后从数组两边向最高点遍历数组。假设相邻连个指针为i和j，如果height[i]>height[j]，如果则向后移动指针j知道大于为止，即为一个凹槽里面的蓄水值
public static int trap(int[] height) {
int maxindex = -1;
int max = -1;
//寻找最高值
for(int i = 0;i<height.length;i++)
if(max<height[i]) {
max = height[i];
maxindex = i;
}
int res = 0;
int i = 0,e = height.length-1;
//正向遍历
while(i<maxindex ) {
int j = i+1;
while(height[j]<height[i] && j<maxindex) {
res += height[i]-height[j];
j++;
}
i = j;
}
//反向遍历
while(e>maxindex ) {
int j = e-1;
while(height[j]<height[e] && j>maxindex) {
res += height[e]-height[j];
j--;
}
e = j;
}
return res;
}
