hot100-42 接雨水

题目描述

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

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

方法一：按列求

求每一列的水，我们只需要关注当前列，以及左边最高的墙，右边最高的墙就够了。

装水的多少，当然根据木桶效应，我们只需要看左边最高的墙和右边最高的墙中较矮的一个就够了。

所以，根据较矮的那个墙和当前列的墙的高度可以分为三种情况:

较矮的墙的高度大于当前列的墙的高度
- 很明显，较矮的一边，减去当前列的高度就可以了
较矮的墙的高度小于当前列的墙的高度
- 正在求的列不会有水，因为它大于了两边较矮的墙。
较矮的墙的高度等于当前列的墙的高度。
- 和上一种情况是一样的，不会有水。

class Solution {
    public int trap(int[] height) {
        int res = 0;
        for(int i=1;i<height.length-1;i++){
            res += findMin(height,i);
        }
        return res;
    }

    private int findMin(int[] height,int curCol){
        int leftHigh = height[curCol];
        int rightHigh = height[curCol];
        int tempLeft = curCol;
        int tempRight = curCol;
        int minHeight;
        int res = 0;

        while(tempLeft>=0){
            if(height[tempLeft]>leftHigh)
                leftHigh = height[tempLeft];
            tempLeft--;
        }
        while(tempRight<=height.length-1){
            if(height[tempRight]>rightHigh)
                rightHigh = height[tempRight];
            tempRight++;
        }
        minHeight = leftHigh>rightHigh?rightHigh:leftHigh;
        if(height[curCol]<minHeight)
            res = minHeight - height[curCol];

        return res;
    }
}

方法二：动态规划

在按列求方法中：对于每一列，我们求它左边最高的墙和右边最高的墙，都是重新遍历一遍所有高度，这里我们可以优化一下。

首先用两个数组，max_left [i] 代表第 i 列左边最高的墙的高度，max_right[i] 代表第 i 列右边最高的墙的高度。（一定要注意下，第 i 列左（右）边最高的墙，是不包括自身的，和 leetcode 上边的讲的有些不同）

对于 max_left 我们其实可以这样求。

max_left [i] = Max(max_left [i-1],height[i-1])。它前边的墙的左边的最高高度和它前边的墙的高度选一个较大的，就是当前列左边最高的墙了。

对于 max_right我们可以这样求。

max_right[i] = Max(max_right[i+1], height[i+1]) 。它后边的墙的右边的最高高度和它后边的墙的高度选一个较大的，就是当前列右边最高的墙了。

class Solution {
    public int trap(int[] height) {
        int res = 0;
        int[] max_left = new int[height.length];
        int[] max_right = new int[height.length];

        for(int i=1;i<height.length-1;i++){
            max_left[i] = Math.max(max_left[i-1],height[i-1]);
        }

        for(int i=height.length-2;i>0;i--){
            max_right[i] = Math.max(max_right[i+1],height[i+1]);
        }

        for(int i=1;i<height.length-1;i++){
            int min_height = Math.min(max_left[i],max_right[i]);
            if(min_height>height[i])
                res += min_height-height[i];
        }

        return res;
    }

}

方法三：双指针

这里要用到两个指针，left 和 right，从两个方向去遍历。

height [ left - 1] 是可能成为 max_left 的变量，同理，height [ right + 1 ] 是可能成为 max_right 的变量。

只要保证 height [ left - 1 ] < height [ right + 1 ] ，那么 max_left 就一定小于 max_right。

因为 max_left 是由 height [ left - 1] 更新过来的，而 height [ left - 1 ] 是小于 height [ right + 1] 的，而 height [ right + 1 ] 会更新 max_right，所以间接的得出 max_left 一定小于 max_right。

反之，我们就从右到左更。

public int trap(int[] height) {
    int sum = 0;
    int max_left = 0;
    int max_right = 0;
    int left = 1;
    int right = height.length - 2; // 加右指针进去
    for (int i = 1; i < height.length - 1; i++) {
        //从左到右更
        if (height[left - 1] < height[right + 1]) {
            max_left = Math.max(max_left, height[left - 1]);
            int min = max_left;
            if (min > height[left]) {
                sum = sum + (min - height[left]);
            }
            left++;
        //从右到左更
        } else {
            max_right = Math.max(max_right, height[right + 1]);
            int min = max_right;
            if (min > height[right]) {
                sum = sum + (min - height[right]);
            }
            right--;
        }
    }
    return sum;
}