题目描述

题目链接

https://leetcode.cn/problems/trapping-rain-water/

思路

1. 动态规划

由题目可知：对于下标，下雨后水能到达的最大高度等于下标两边的最大高度的最小值，下标处能接的雨水量等于下标处的水能到达的最大高度减去。

朴素的做法是对于数组中的每个元素，分别向左和向右扫描并记录左边和右边的最大高度，然后计算每个下标位置能接的雨水量。假设数组的长度为，该做法需要对每个下标位置使用的时间向两边扫描并得到最大高度，因此总时间复杂度是。

上述做法的时间复杂度较高是因为需要对每个下标位置都向两边扫描。如果已经知道每个位置两边的最大高度，则可以在的时间内得到能接的雨水总量。使用动态规划的方法，我们可以在的时间内预处理得到每个位置两边的最大高度。

创建两个长度为的数组和。对于，表示下标及其左边的位置中的最大高度，表示下标及其右边的位置中的最大高度。显然，初始条件为：，。数组中其余元素的计算如下：

• 当时，
• 当时，

因此可以正向遍历数组得到数组的每个元素值，反向遍历数组得到数组的每个元素值。在得到数组和的每个元素值之后，对于，下标处能接的雨水量等于。遍历每个下标位置即可得到能接的雨水总量。

动态规划做法可以由下图体现：

具体代码实现如下：

public int trap(int[] height) {
    if (height == null || height.length == 0) {
        return 0;
    }
    // 预处理leftMax
    int n = height.length;
    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]);
    }
    // 预处理rightMax
    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]);
    }
    // 计算雨水总量
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += Math.min(leftMax[i], rightMax[i]) - height[i];
    }
    return ans;
}

• 时间复杂度：，其中是数组的长度。计算数组和的元素值各需要遍历数组一次，计算能接的雨水总量还需要遍历一次。
• 空间复杂度：，其中是数组的长度。需要创建两个长度为的数组和。

  2. 单调栈

  除了方法一中计算并存储每个位置两边的最大高度以外，也可以用「单调栈」计算能接的雨水总量。我们维护一个单调栈，单调栈存储的是下标，满足从栈底到栈顶的下标对应的数组中的元素递减，即栈顶元素对应的数组中的值是当前栈中最小的。

从左到右遍历数组，遍历到下标时，如果栈内至少有两个元素，记栈顶元素为，的下面一个元素是，则一定有。如果，则得到一个可以接雨水的区域，该区域的宽度是，高度是，根据宽度和高度即可计算得到该区域能接的雨水量。

为了得到，需要将出栈。在对计算能接的雨水量之后，变成新的，重复上述操作，直到栈变为空，或者栈顶下标对应的中的元素大于或等于。在对下标处计算能接的雨水量之后，将入栈，继续遍历后面的下标，计算能接的雨水量。遍历结束之后即可得到能接的雨水总量。

下面用一个例子来帮助理解单调栈的做法。 具体代码实现如下：

public int trap(int[] height) {
    if (height == null || height.length == 0) {
        return 0;
    }
    int ans = 0;
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < height.length; i++) {
        // 保持栈顶到栈底对应的height数组中的元素是递减的(单调栈)
        while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
            int top = stack.pop();
            if (stack.isEmpty()) {
                break;
            }
            // 计算雨水面积
            int left = stack.peek();
            int curWidth = i - left - 1;
            int curHeight = Math.min(height[left], height[i]) - height[top];
            ans += curWidth * curHeight;
        }
        stack.push(i);
    }
    return ans;
}

• 时间复杂度：，其中是数组的长度。从到的每个下标最多只会入栈和出栈各一次。
• 空间复杂度：，其中是数组的长度。空间复杂度主要取决于栈，栈的大小不会超过。

  3. 双指针

  动态规划的做法中，需要维护两个数组和，因此空间复杂度是。是否可以将空间复杂度降到呢？答案是可以的，注意到下标处能接的雨水量由和中的最小值决定。由于数组是从左往右计算，数组是从右往左计算的，因此可以使用双指针和两个变量代替两个数组。

维护两个指针和以及两个变量和，初始时、、、。指针只会向右移动，指针只会向左移动，在移动指针的过程中动态维护两个变量和的值。

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

• 使用和的值更新和的值；

• 如果，则必有，下标处能接的雨水量等于，将下标处能接的雨水量加到能接的雨水总量，然后将右移一位；

• 如果，则必有，下标处能接的雨水量等于，将下标处能接的雨水量加到能接的雨水总量，然后将减去，即左移一位。

当两个指针相遇时，即可得到能接的雨水总量。下面用一个例子来帮助理解双指针的做法。 具体代码实现如下：

public int trap(int[] height) {
    int ans = 0;
    int left = 0, right = height.length - 1;
    int leftMax = 0, rightMax = 0;
    // 按照列来求面积
    while (left < right) {
        // 动态维护leftMax、rightMax的值
        leftMax = Math.max(leftMax, height[left]);
        rightMax = Math.max(rightMax, height[right]);
        // 雨水容量取决于 max 值减当前值
        if (height[left] < height[right]) {
            ans += leftMax - height[left];
            // 右移
            left++;
        } else {
            ans += rightMax - height[right];
            // 左移
            right--;
        }
    }
    return ans;
}

• 时间复杂度：，其中是数组的长度。两个指针的移动总次数不超过。
• 空间复杂度：，只需要使用常数的额外空间。