42.接雨水

链接

思路

当计算一个块时，是使用当前块左边和右边的最高值，然后这两个最高值取最小值，得到的这个值再减去当前块的高度即可。

大致思路就是这样子，有两种方式可以去解答。第一种先分别求出每一个块的左边最大和右边最大。然后循环获得答案，注意如果说，当前块的高度是大于左边右边最大值那么直接舍弃。

第二种方式是使用双向双指针算法，定义左右最大值进行比较，每一次都记录最大值，leftMax < rightMax说明需要使用leftMax来作为当前的高度。

代码

class Solution {
    public int trap(int[] h) {

        int n = h.length;
        int ans = 0;
        int left = 0;
        int right = n - 1;
        int leftMax = 0;
        int rightMax = 0;

        while (left < right) {
            leftMax = Math.max(leftMax, h[left]);
            rightMax = Math.max(rightMax, h[right]);

            if (leftMax < rightMax) ans += leftMax - h[left++];
            else ans += rightMax - h[right--];
        }

        return ans;
    }
}