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

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 6k 阅读时长 ≈ 5 分钟

By Long Luo

Leetcode 42. 接雨水 题目如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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

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

思路与算法：

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

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

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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\)，然后继续循环。

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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])\)。

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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]\) 数组中的元素其实只用到了一次，所以可以只用一个元素就行了。

很容易写出如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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}\)，代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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\) 入栈，继续遍历后面的下标，计算能接的雨水量。遍历结束之后即可得到能接的雨水总量。

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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. 😉😃💗