T42、接雨水

给定 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;
    }