【动态规划, 双指针, 栈】接雨水

题目

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 个单位的雨水（蓝色部分表示雨水）。 

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

• n == height.length
• 1 <= n <= 2 * 10^4
• 0 <= height[i] <= 10^5

解题

方法一：暴力 快慢指针 按行求(超时)

思路

先找出数组中最大的数(max)作为最大的行数。

求第 row 行的水，遍历每个位置，如果当前的高度小于 row，并且两边有高度大于等于 row 的，说明这个地方一定有水，水就可以加 1。

因为数组两边之外是没有墙的，不能在 $[0, ?]$ 存水，所以需要一个变量(isStart)在从左到右遇到第一赌墙的时候标记可以开始存水了，再声明一个变量用于记录能接多少雨水(ans)。

快慢指针(slow, quick)从 0 开始遍历，如果快指针指向的元素大于等于当前的行数，则说明快指针指向了当前行中的一堵墙：

• 如果还不能开始存水(isStart == false)就说明遇到了第一堵墙，修改标记(usStart= reue)表示可以开始存水了，并把慢指针直接移到快指针的位置
• 如果可以存水了，就把从慢指针到快指针的区域($slow+1 \to quick-1$)全部存上水(ans += quick-slow-1)。并把慢指针移到快指针的位置（如果快慢指针是两堵相邻的墙，可存水的区域算出来是 0 ，不用担心）。
• 快指针后移进行下一次遍历

代码

class Solution {
    public int trap(int[] height) {
        int len = height.length;
        int max = 0, ans = 0;
        for (int h : height) max = Math.max(max, h);
        for (int row = 1; row <= max; row++) {
            boolean isStart = false;
            for (int slow = 0, quick = 0; quick < len; quick++) {
                if (height[quick] >= row) {
                    if (!isStart) {
                        slow = quick;
                        isStart = true;
                        continue;
                    } 
                    ans += quick - slow - 1;
                    slow = quick;
                }
            }
        }
        return ans;
    }
}

方法二：暴力 按列求

思路

求每一列的水，只需要关注当前列，以及左边最高的墙，右边最高的墙就够了。 装水的多少，当然根据木桶效应，只需要看左边最高的墙和右边最高的墙中较矮的一个就够了。 所以，根据较矮的那个墙和当前列的墙的高度可以分为三种情况：

1. 较矮的墙的高度大于当前列的墙的高度 把正在求的列左边最高的墙和右边最高的墙确定后，为了方便理解，把无关的墙去掉。 现在往两边最高的墙之间注水，很明显，较矮的一边，也就是左边的墙的高度，减去当前列的高度就可以了，也就是 $2 - 1 = 1$，可以存一个单位的水。

2. 较矮的墙的高度小于当前列的墙的高度 同样把其他无关的列去掉。 |

   往两边最高的墙之间注水，正在求的列不会有水，因为它大于了两边较矮的墙。

3. 较矮的墙的高度等于当前列的墙的高度 和上一种情况是一样的，不会有水。

明白了这三种情况，程序就很好写了，遍历每一列，然后分别求出这一列两边最高的墙。找出较矮的一端，和当前列的高度比较，结果就是上边的三种情况。

代码

class Solution {
    public int trap(int[] height) {
        int len = height.length;
        int ans = 0;
        for (int i = 1; i < len - 1; i++) {
            int leftMax = getRangeMax(height, 0, i - 1);
            int rightMax = getRangeMax(height, i + 1, len - 1);
            ans += Math.max(0, Math.min(leftMax, rightMax) - height[i]);
        }
        return ans;
    }

    private int getRangeMax(int[] nums, int start, int end) {
        int max = nums[start];
        for (int i = start; i <= end; i++) {
            if (nums[i] > max) max = nums[i]; 
        }
        return max;
    }
}

方法三：动态规划 按列求

思路

解法二中，对于每一列，求它左边最高的墙和右边最高的墙，都是重新遍历一遍所有高度，这里可以利用动态规划的思想优化一下。

首先用两个数组，leftMax[i]代表第 i 列左边最高的墙的高度，rightMax[i] 代表第 i 列右边最高的墙的高度。（注意：第 i 列左（右）边最高的墙，是不包括自身的）。

对于 leftMax 有：$leftMax[i] = max(leftMax[i - 1], height[i - 1])$，即从它前边的墙的左边的最高高度和它前边的墙的高度选一个较大的，就是当前列左边最高的墙了 。 同样的，对于 rightMax 有：$rightMax[i] = max(rightMax[i + 1], height[i + 1])$

之后再利用解法二的算法即可。

代码(计算范围最大时不包含当前)

class Solution {
    public int trap(int[] height) {
        int len = height.length;
        int[] leftMax = new int[len], rightMax = new int[len];
        for (int i = 1; i < len; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i - 1]);
        }
        for (int i = len - 2; i >= 0 ; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i + 1]);
        }
        int ans = 0;
        for (int i = 1; i < len - 1; i++) {
            ans += Math.max(0, Math.min(leftMax[i], rightMax[i]) - height[i]);
        }
        return ans;
    }
}

代码(计算范围最大时包含当前)

class Solution {
    public int trap(int[] height) {
        int len = height.length;
        int[] leftMax = new int[len], rightMax = new int[len];
        leftMax[0] = height[0];
        for (int i = 1; i < len; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }
        rightMax[len - 1] = height[len - 1];
        for (int i = len - 2; i >= 0 ; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }
        int ans = 0;
        for (int i = 1; i < len - 1; i++) {
            ans += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
}

优化

因为 leftMax[] 中的值只会用一次，可以用滚动数组的思想优化掉，在计算能接 多少雨水时计算即可

class Solution {
    public int trap(int[] height) {
        int len = height.length;
        int leftMax = height[0];
        int[] rightMax = new int[len];
        for (int i = len - 2; i >= 0 ; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i + 1]);
        }
        int ans = 0;
        for (int i = 1; i < len - 1; i++) {
            leftMax = Math.max(leftMax, height[i - 1]);
            ans += Math.max(0, Math.min(leftMax, rightMax[i]) - height[i]);
        }
        return ans;
    }
}

方法四：双指针

思路

左右双指针(left, right)同时开两个柱子接水。在前两种解法我们知道对于每一个柱子接的水，那么有：

$当前柱子能接的水=min(左最高柱子, 右最高柱子) - 当前柱子高度$

同样的，两根柱子要一起求接水，同样要知道它们左右两边最大值的较小值。

问题就在这，假设两柱子分别为 left，right。那么就有 lLeftMax,lRightMax,rLeftMax,rRightMax这四个变量。由于 left > right ，故有：

• rLeftMax >= lLeftMax(即右指针左边的最高柱子高度 >= 左指针左边最高柱子高度)
• lRigthMax >= rRightMax(即左指针右边的最高柱子高度 >= 右指针右边的最高柱子高度)

那么，如果 ：

• lLeftMax < rRightMax，则必有 lRightMax > lLeftMax，左指针(left)可以接水
• lLeftMax >= rRightMax，则必有 rLeftMax >= rRightMax，右指针(right)可以接水

而上面实际上只用到了 lLeftMax，rRightMax 两个变量，故我们维护这两个即可。

代码

class Solution {
    public int trap(int[] height) {
        int len = height.length;
        int left = 1, right = len - 2;
        int lLeftMax = height[0], rRightMax = height[len - 1];
        int ans = 0;
        while (left <= right) {
            lLeftMax = Math.max(lLeftMax, height[left]);
            rRightMax = Math.max(rRightMax, height[right]);
            if (lLeftMax < rRightMax) {
                ans += lLeftMax - height[left];
                left++;
            } else {
                ans += rRightMax - height[right];
                right--;
            }
        }
        return ans;
    }
}

方法五：单调递减栈

思路

维护一个单调栈，单调栈存储的是下标，满足从栈底到栈顶的下标对应的数组 height 中的元素递减。 从左到右遍历数组，记遍历索引为 right，如果遍历到某个索引时栈内至少有两个元素，记栈顶元素为 curr，则其对应高度为 currHeight，其下面一个元素为 left，则一定有 $height[left] \geq currHeight$ 。如果 $height[right] > currHeight$ 则得到一个可以接雨水的区域，该区域的宽度是 $areaWidth = right - left - 1$ 高度是 $areaHeight = min(rightHeight, height[left]) - currHeight$，则该区域可接的雨水量为 $areaWidth * areaHeight$。 为了得到 left，需要将获取 currHeight 的栈顶元素 curr 出栈。在对 curr 计算能接的雨水量之后，left 变成新的 curr，重复上述操作，直到栈变为空，或者 currHeight >= height[right]。 在对下标 $right$ 处计算能接的雨水量之后，将 right 入栈，继续遍历后面的下标，计算能接的雨水量。遍历结束之后即可得到能接的雨水总量。

代码

class Solution {
    public int trap(int[] height) {
        Deque<Integer> monoStack = new LinkedList<>();
        int ans = 0;
        for (int right = 0; right < height.length; right++) {
            int rightHeight = height[right];
            while (!monoStack.isEmpty() &&
                   rightHeight > height[monoStack.peek()]) {
                int currHeight = height[monoStack.pop()];
                if (monoStack.isEmpty()) break;
                int left = monoStack.peek();
                int areaWidth = right - left - 1;
                int areaHeight = Math.min(rightHeight, height[left]) - currHeight;
                ans += areaWidth * areaHeight;
            }
            monoStack.push(right);
        }
        return ans;
    }
}