LeetCode-42-接雨水

题目

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

示例 1：

img

输入：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 * 104
• 0 <= height[i] <= 105

题解

法一：动态规划

本题求解的思路为：对于i处，下雨后水能达到的最大高度为i位置左右两边最大高度的最小值，然后i处能接到的雨水量为i处水能达到的最大高度减去height[i]。

这里我们使用两个数组leftMax、rightMax，leftMax表示i处左边的最大高度，rightMax表示i处右边的最大高度；

1. 首先leftMax与rightMax初始化，leftMax[0] = height[0]，rightMax[n - 1] = height[n - 1]
2. 对于leftMax，我们从1开始遍历height数组，leftMax[i] = max(leftMax[i - 1], height[i])
3. 对于rightMax，从n - 2处开始倒着遍历height数组，rightMax[i] = max(rightMax[i + 1], height[i])
4. 最后我们取ans = min(leftMax[i], rightMax[i]) - height[i]，再累加求和即可

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) {
            return 0;
        }

        // 表示第i个位置左边最高的高度
        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for(int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }
        // 表示第i个位置右边的最高高度
        int[] rightMax = new int[n];
        rightMax[n - 1] = height[n - 1];
        for(int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        // 计算结果，结果为左右两端最大值的最小值与height[i]的差
        int ans = 0;
        for(int i = 0; i < n; i++) {
            ans += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
}

方法二：单调栈

除了计算并存储每个位置两边的最大高度以外，也可以用单调栈计算能接的雨水总量。

维护一个单调栈，单调栈存储的是下标，满足从栈底到栈顶的下标对应的数组height中的元素递减。

从左到右遍历数组，遍历到下标i时，如果栈内至少有两个元素，记栈顶元素为 top，top的下面一个元素是left，则一定有height[left] >= height[top]。如果height[i] > height[top]，则得到一个可以接雨水的区域，该区域的宽度是i - left - 1，高度是min(height[left], height[i]) - height[top]，根据宽度和高度即可计算得到该区域能接的雨水量。

为了得到left，需要将top出栈。在对top计算能接的雨水量之后，left变成新的top，重复上述操作，直到栈变为空，或者栈顶下标对应的 height中的元素大于或等于height[i]。

在对下标i处计算能接的雨水量之后，将i入栈，继续遍历后面的下标，计算能接的雨水量。遍历结束之后即可得到能接的雨水总量。

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

方法三：双指针

动态规划的做法中，需要维护两个数组leftMax和rightMax，因此空间复杂度是O(n)。是否可以将空间复杂度降到O(1)？

注意到下标i处能接的雨水量由leftMax[i]和rightMax[i]中的最小值决定。由于数组leftMax是从左往右计算，数组rightMax是从右往左计算，因此可以使用双指针和两个变量代替两个数组。

维护两个指针left和right，以及两个变量leftMax和rightMax，初始时left = 0, right = n − 1, leftMax = 0, rightMax = 0。指针left只会向右移动，指针right只会向左移动，在移动指针的过程中维护两个变量leftMax和rightMax的值。

当两个指针没有相遇时，进行如下操作：

使用height[left]和height[right]的值更新leftMax和rightMax的值；

如果height[left] < height[right]，则必有leftMax<rightMax，下标left处能接的雨水量等于leftMax − height[left]，将下标left处能接的雨水量加到能接的雨水总量，然后将left加1（即向右移动一位）；

如果height[left] ≥ height[right]，则必有leftMax ≥ rightMax，下标right 处能接的雨水量等于rightMax − height[right]，将下标right处能接的雨水量加到能接的雨水总量，然后将right减 1（即向左移动一位）。

当两个指针相遇时，即可得到能接的雨水总量。

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

以上内容参考于：

42. 接雨水 - 力扣（LeetCode）