接雨水

QUESTION:

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。 img

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6

EXPLANATION:

思路是：从头开始向尾循环，记录当前最高的maxheight，如果遇到比这个maxheight矮的，那么就可以获取到maxheight-当前的水，如果比maxheight高，那么就可以将maxheight换成新的最大值，但是这样有一个问题，那就是在遇到数组最大值后，后面的数组会多算。那么就可以从两边往中间来进行，这样就能保证最后计算的是最大值。那么就能算出正确的雨水。
1.定义两个指针用来标记index，同时定义两个max来标记左右最大值
2.如果height[left]<height[right]那就说明right的值比较大，那么就需要往right靠
3.同时在往right靠的时候，需要查看当前水柱是不是比最大值小，这样就能计算出储水的值
4.最后当left>right也就是计算到了最后的最大值了，就可以获取到正确的答案

SOLUTION:

class Solution {
    public int trap(int[] height) {
        if(height == null || height.length<=2) return 0;
        int left = 0,right = height.length-1,result = 0,leftHeight = 0,rightHeight = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftHeight) leftHeight = height[left];
                else result += leftHeight - height[left];
                left++;
            } else {
                if (height[right] >= rightHeight) rightHeight = height[right];
                else result += rightHeight - height[right];
                right--;
            }
        }
        return result;
    }
}
>
--> return <--