【力扣高频题】042.接雨水问题

上一篇我们通过采用 双指针 的方法解决了 经典 容器盛水 问题 ，本文我们接着来学习一道在面试中极大概率会被考到的经典题目：接雨水 问题 。

42. 接雨水

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

示例 1：

输入： height = [0,1,0,2,1,0,1,3,2,1,2,1]

输出： 6

解释： 在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

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

思路分析

边界条件： 如果只有 一个 或 两个 柱子，一定是接不到水的。

我们考虑每个柱子的接水情况，当前列能够接多少水，取决于 当前列的高度 以及 左右两侧的最大高度 。

与 上一道题 思想类似：能够装多少水量，取决于两端 较短 的竖线的 长度 。

因此，大致思路就浮现出来了：

对于下标 i 位置的柱子来说，只需计算出左右两侧最大高度的 最小值（即能够达到的最大高度），与当前列的高度 作差 ，即可知道当前列的接水量。

遍历整个数组，将每个位置的接水量进行累加，即可得到最终的接水量。

注意：

1. 若当前列的高度大于等于左右两侧最大高度的最小值时，接水量为 0 （要避免负值的出现）。
2. 左右两侧边界处 不会有接水量 ，因此从第二个柱子遍历到倒数第二个柱子即可。

暴力代码

public int trap(int[] height) {
    int water = 0;
    // 左右两侧边界不考虑
    for (int i = 1; i < height.length - 1; i++) {
        int leftMax = 0;
        // 找出左侧的最大值
        for (int j = i - 1; j >= 0; j--) {
            if (height[j] > leftMax) {
                leftMax = height[j];
            }
        }
        int rightMax = 0;
        // 找出右侧的最大值
        for (int j = i + 1; j < height.length; j++) {
            if (height[j] > rightMax) {
                rightMax = height[j];
            }
        }
        // 左右两侧最大高度的 最小值
        int min = Math.min(leftMax, rightMax);
        // 当大于当前列的高度时才有接水量
        if (min > height[i]) {
            water += min - height[i];
        }
    }
    return water;
}
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

暴力法分析

在该方法中，对于每个数组元素的求解，都需要 $O(n)$ 的时间复杂度向左右两端遍历整个数组，得到最大值。因此总的时间复杂度为 $O(n^2)$ 。空间复杂度为 $O(1)$ 。

思路优化

接下来我们仍采取 双指针的思想 进行优化。

由于当前位置的接水量取决于左右两侧最大值的较小值。因此，可以设置左右指针进行更新。

1. 设置 L 和 R 双指针记录当前要计算的是 哪个位置 的接水量。

2. 设置两个最大值的变量 leftMax 和 rightMax ，用来记录处于当前位置时，左右两侧的 最大值 。

最大值哪侧更小，就说明此时可以计算出哪侧的接水量了，并记得更新该侧的最值（看此时的高度是否超过了之前的最值高度），之后往下移动。

直至两个指针相遇后，计算出了总的接水量。

优化代码

public static int trap(int[] arr) {
    if (arr == null || arr.length < 3) {
        return 0;
    }
    int N = arr.length;
    int L = 1;
    int leftMax = arr[0];
    int R = N - 2;
    int rightMax = arr[N - 1];
    int water = 0;
    while (L <= R) {
        if (leftMax <= rightMax) {
            water += Math.max(0, leftMax - arr[L]);
            leftMax = Math.max(leftMax, arr[L++]);
        } else {
            water += Math.max(0, rightMax - arr[R]);
            rightMax = Math.max(rightMax, arr[R--]);
        }
    }
    return water;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

复杂度分析

左右两个指针的移动次数不超过数组的长度，因此时间复杂度为 $O(n)$ 。空间复杂度为 $O(1)$ 。

---

这道题目主要考察了使用 双指针 优化频繁遍历的思想，是算法题中经常出现的考察形式。小伙伴们一定要牢牢掌握哦~

~ 点赞 ~ 关注 ~ 星标 ~ 不迷路 ~！！！

回复「ACM紫书」获取 ACM 算法书籍 ~
回复「算法导论」获取 算法导论第3版 ~

在看 + 转发

让你的小伙伴们一起来学算法吧！！