[Leetcode][42. 接雨水] 5种解法：木桶原理，按行求，动态规划，双指针，单调栈

发表于 2021-10-19 更新于 2022-09-30 分类于 Data Structures and Algorithms 阅读次数：本文字数： 6.9k 阅读时长 ≈ 6 分钟

By Long Luo

42. 接雨水

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

示例 1：

![接雨水 1](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/10/22/rainwatertrap.png)

输入：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

方法一：按列求（木桶原理）

思路与算法：

很容易想到，装水的多少，根据木桶原理，只需要关注左边最高的木板和右边最高的模板中较矮的一个就够了，那么存储的水，等于两边木板的较小值减去当前高度的值。

从左向右遍历数组：
- 从当前元素向左扫描并更新： $\text{max\_left}=\max(\text{max\_left}, \text{height}[j])$
- 从当前元素向右扫描并更新： $\text{max\_right}=\max(\text{max\_right}, \text{height}[j])$
更新 $\text{ans} += \min(\text{max\_left}, \text{max\_right}) - \text{height}[i]$ 。

代码如下所示：

public static int trap(int[] height) {
    if (height == null || height.length <= 2) {
        return 0;
    }

    int ans = 0;
    int len = height.length;
    for (int i = 1; i < len - 1; i++) {
        int maxRight = 0;
        int maxLeft = 0;
        for (int right = i; right < len; right++) {
            maxRight = Math.max(maxRight, height[right]);
        }

        for (int left = i; left >= 0; left--) {
            maxLeft = Math.max(maxLeft, height[left]);
        }

        ans += Math.min(maxLeft, maxRight) - height[i];
    }

    return ans;
}

复杂度分析：

时间复杂度： $O(n^2)$ ，遍历每一列需要 $n$ ，找出左边最高和右边最高的木板加起来刚好又是一个 $n$ ，所以是 $n^2$ 。
空间复杂度： $O(1)$ 。

方法二：按行求

思路与算法：

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

如果求高度为 $i$ 的水，首先用一个变量 $water$ 保存当前累积的水，初始化为 $0$ 。从左到右遍历墙的高度，遇到 $h \ge i$ 的时候，开始更新 $water$ 。

第一次遇到已经开始计算时并且 $h < i$ 的就把 $water+1$ ，再次遇到 $h \ge i$ 的，说明这个地方一定有水，就把 $water$ 加到最终的答案 $ans$ 里， $water=0$ ， $flag=false$ ，然后继续循环。

代码如下所示：

public static int trap_row(int[] height) {
    if (height == null || height.length <= 2) {
        return 0;
    }

    int ans = 0;
    int len = height.length;
    int maxHeight = 0;

    for (int x : height) {
        maxHeight = Math.max(maxHeight, x);
    }

    for (int i = 1; i <= maxHeight; i++) {
        boolean flag = false;
        int water = 0;
        for (int j = 0; j < len; j++) {
            if (flag && height[j] < i) {
                water++;
            }

            if (height[j] >= i) {
                ans += water;
                water = 0;
                flag = true;
            }
        }
    }

    return ans;
}

复杂度分析：

时间复杂度： $O(maxHeight \times n)$ ，其中 $maxHeight$ 是数组元素的最大值。
空间复杂度： $O(1)$ 。

方法三：动态规划

思路与算法：

方法一中对于每一列，我们求它左边最高的木板和右边最高的木板，都需要遍历一遍所有高度，这里可以优化一下。

我们使用两个数组， $leftMax[i]$ 代表第 $i$ 列左边最高的木板的高度， $rightMax[i]$ 代表第 $i$ 列右边最高的木板的高度，注意这里第 $i$ 列左（右）边最高的木板，是不包括自身的。

$leftMax[i] = Max.max(leftMax[i-1], height[i-1])$ ，当前列左边最高的木板要么是它左边的木板，要么是左边木板左边的最高高度。

同理 $rightMax[i] = Math.max(max_right[i+1], height[i+1])$ 。

代码如下所示：

public static int trap_dp(int[] height) {
    if (height == null || height.length <= 2) {
        return 0;
    }

    int ans = 0;
    int len = height.length;
    int[] leftMax = new int[len];
    int[] rightMax = new int[len];
    for (int i = 1; i < len - 1; 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]);
    }

    for (int i = 1; i < len - 1; i++) {
        int min = Math.min(leftMax[i], rightMax[i]);
        ans += min > height[i] ? min - height[i] : 0;
    }

    return ans;
}

复杂度分析：

时间复杂度： $O(n)$ 。
空间复杂度： $O(n)$ 。

方法四：双指针

思路与算法：

一般来说，动态规划的空间复杂度都可以进行优化。从方法三也可以看出， $leftMax[i]$ 和 $rightMax[i]$ 数组中的元素其实只用到了一次，所以可以只用一个元素就行了。

很容易写出如下代码：

public static int trap_tp(int[] height) {
    if (height == null || height.length <= 2) {
        return 0;
    }

    int len = height.length;
    int ans = 0;
    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]);
    }

    for (int i = 1; i < len - 1; i++) {
        leftMax = Math.max(leftMax, height[i]);
        int min = Math.min(leftMax, rightMax[i]);
        ans += min > height[i] ? min - height[i] : 0;
    }

    return ans;
}

上述代码的空间复杂度还是 $O(n)$ ，如何才能把 $rightMax$ 的数组也去掉呢？

因为从左往右处理到 $i$ 下标时，左边的最大值 $leftMax$ 是可信的，因为 $rightMax$ 是从右往左遍历的，所以需要 $rightMax$ 数组来记录右边最大值。

基于此，要用到两个指针， $left$ 和 $right$ ，从两个方向去遍历。

如果一端有更高的木板，那么水的高度依赖于当前方向的高度（从左到右），而当我们发现另一侧（右侧）的木板不是最高的，则开始从相反的方向遍历（从右到左）。

我们可以只需要 $1$ 次遍历，在遍历时同时维护 $\text{leftMax}$ 和 $\text{rightMax}$ ，代码如下所示：

public static int trap_tp_opt(int[] height) {
    if (height == null || height.length <= 2) {
        return 0;
    }

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

    return ans;
}

复杂度分析：

时间复杂度： $O(n)$ 。
空间复杂度： $O(1)$ 。

方法五：单调栈

思路与算法：

遍历到某些木板的时候，会由于和之前的某个木板形成凹形的坑，从而可以接住雨水，所以这道题目可以用单调栈来做。

单调栈就是比普通的栈多一个性质，即维护一个栈内元素单调。使用单调栈来解，和方法二类似，但又有所区别。具体到这道题，单调栈存储的是下标，满足从栈底到栈顶的下标对应的 $\textit{height}[idx]$ 递减。

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

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

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

代码如下所示：

public static int trap_stack_opt(int[] height) {
    int ans = 0;
    Deque<Integer> stack = new LinkedList<Integer>();
    int len = height.length;
    for (int i = 0; i < len; 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;
}

复杂度分析：

时间复杂度： $O(n)$ 。
空间复杂度： $O(n)$ 。

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗

方法一： 按列求（木桶原理）

方法二：按行求

方法三：动态规划

方法四：双指针

方法五：单调栈

方法一：按列求（木桶原理）