本篇文章比较长，可以点击右侧齿轮按钮，打开侧边栏，会显示出目录方便大家查看。目录下滑会自动展开。🎉

接雨水

题目描述

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

数据样例

示例 1

1
2
3
输入：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

1
2
输入：height = [4,2,0,3,2,5]
输出：9

提示：

  • $n == height.length$
  • $1 \leq n \leq 2 * 10 ^ 4$
  • $0 \leq height[i] \leq 10 ^ 5$

木桶原理

木桶原理扩展：对于基础木桶原理而言，我们知道木桶可以装入的水量取决于当前木桶所有木板中最短的那个

那么对其进行扩展，如上图中所示，我们可以知道：对于上述红色框中可以看作是一个木桶，那么 对于木桶中的每个位置，其可以装入的水量取决于 两侧 木板高度小的那个木板高度。

注意：我们计算的是木桶中的每个位置，也就是木桶中的每个柱子，并不是直接计算木桶中可以装入的水量

因此我们可以知道：对于当前位置 $i$，其柱子高度为 $height[i]$，则其可以装入的水的量取决于：

  • 从当前位置向左找，找到最高的柱子（相对于是木桶的左侧的木板），记为 $left$
  • 从当前位置向右走，找到最高的柱子（相对于是木桶的右侧的木板），记为 $right$

那么可以知道当前位置可以装入的水量：$min(left, right) - height[i]$

PS：这里注意，如果 $min(left, right) \leq height[i]$，那么就无法装入水

方法 1：枚举 + 优化 - $O(N ^ 2)$

枚举

我们知道如何计算每个位置可以装入的水量，那么总体水量：

  • 依次枚举所有的位置
  • 找到左侧和右侧最高的柱子，然后计算当前可以转入的水量
  • 将所有位置可以装入的水量累加起来

枚举优化

如果直接按照上述枚举的方法，无法通过 LeetCode 测试

我们可以观察一下是否可以对枚举的过程进行优化

我们发现，可以在 $i$ 枚举过程中顺带计算左侧最高的柱子：

  • $i$ 从左往右枚举过程中，利用变量 $left$ 记录 $i$ 枚举过的所有柱子中的最高柱子

那么每次 只需要枚举得到右侧最高柱子 即可

经过优化后，可以通过 LeetCode

时间复杂度 - $O(N ^ 2)$

  • 每个位置需要遍历整个数组：$O(N ^ 2)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func trap(height []int) int {
    // res: 记录答案：每个位置水量和
    n, res := len(height), 0
    // i 指针从前往后枚举每个位置，left：枚举优化，顺带计算左侧柱子最大值
    for i, left := 0, 0; i < n; i++ {
        left = max(left, height[i])
        // right：计算右侧柱子的最大值，j 指针从后往前枚举所有的位置，依次计算得到最大值
        right := height[i]
        for j := i + 1; j < n; j++ { right = max(right, height[j]) }
        // 木桶效应：当前数量取决于两侧木板小的那个
        res += min(left, right) - height[i]
    }
    return res
}

func min(x, y int) int { if x < y { return x }; return y }
func max(x, y int) int { if x > y { return x }; return y }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int res = 0;
        for (int i = 0, left = 0; i < n; ++i) {
            left = max(left, height[i]);
            int right = height[i];
            for (int j = i + 1; j < n; ++j) right = max(right, height[j]);
            res += min(left, right) - height[i];
        }
        return res;
    }
};

方法 2：动态规划 - $O(N)$

动态规划

我们回顾一下枚举方法，我们每次枚举每个位置的时候，都需要枚举一遍数组得到左侧最大值和右侧最大值（最高的柱子）

那么由于这个值在题目给定柱子高度后就已经确定了，那么可以在枚举每个位置之前，先将每个位置的左侧和右侧的最大值计算出来。

考虑当前位置 $i$ 的左侧的最大值：$left[i]$:

  • 第一种可能：当前位置（柱子）是最高的：$height[i]$
  • 第二种可能：前面某个柱子是最高的: $left[i - 1]$

$$left[i] = max(left[i - 1], height[i])$$

对于右侧而言，同理：
$$right[i] = max(right[i - 1], height[i])$$

得到 $left[], right[]$ 数组后，枚举每个位置的时候，就不需要遍历整个数组寻找左侧和右侧的最大值了。

时间复杂度 - $O(N)$

  • 枚举每个位置的时候不需要枚举寻找最大值，只需要查询数组 $left[i], right[i]$ 即可，因此复杂度为 $O(N)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func trap(height []int) int {
    n, res := len(height), 0
    // left，right两个数组，分别用于记录每个位置前面和后面的柱子的最大值
    left, right := make([]int, n), make([]int, n)
    // 动态规划过程，依次枚举每个位置，计算得到这两个数组left, right
    left[0], right[n - 1] = height[0], height[n - 1]
    for i := 1; i < n; i++ { left[i] = max(left[i - 1], height[i]) }
    for i := n - 2; i >= 0; i-- { right[i] = max(right[i + 1], height[i]) }
    // 枚举所有位置，木桶效应计算当前位置可以容纳的水量
    for i := 0; i < n; i++ { res += min(left[i], right[i]) - height[i] }
    return res
}

func min(x, y int) int { if x < y { return x }; return y }
func max(x, y int) int { if x > y { return x }; return y }
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> left(n), right(n);
        left[0] = height[0], right[n - 1] = height[n - 1];
        for (int i = 1; i < n; ++i) left[i] = max(left[i - 1], height[i]);
        for (int i = n - 2; i >= 0; --i) right[i] = max(right[i + 1], height[i]);
        int res = 0;
        for (int i = 0; i < n; ++i) res += min(left[i], right[i]) - height[i];
        return res;
    }
};

方法 3：双指针 - $O(N)$

双指针

这个题目双指针算法可能 不容易想到，如果没想到的同学不要灰心呀，加油！。

我们考虑最初讲解的枚举：$i$ 指针每次枚举每个位置，$j$ 指针对于每个位置，枚举得到左侧和右侧的最大值

我们考虑 是否对于 $i$ 指针每次枚举的每个位置，$j$ 指针都需要从头枚举一遍整个数组得到左侧和右侧的最大值呢？

  • 首先我们根据之前讲解的 枚举优化，可以知道，$j$ 不需要枚举 $i$ 左侧的所有柱子
    • 这些柱子可以通过 $i$ 指针枚举的过程中顺带计算得到。我们记左侧的最大值为 $left$

$j$ 是否需要每次从 $i$ 开始枚举一遍右侧呢？

  • 我们发现，当 $j$ 指针向右侧枚举的过程中，如果 $height[j] \geq left$ 的时候，此时就不需要继续枚举了
    • 由于之前讲解的 木桶原理，此时，后面柱子的最大值：$rigth \geq height[j] \geq left$，因此当前位置对应木桶两个木板的最小值就是：$min(left, right) = left$ 了

现在我们知道当 $height[j] \geq left$ 的时候，可以停止遍历，但是 $j$ 对于每次 $i$ 位置而言，都需要从后面往前遍历，那么复杂度依然是 $O(N ^ 2)$

此时，我们首先改变一下 $j$ 枚举的顺序：改为 从后往前遍历

$j$ 是否每次都需要从最后面开始遍历呢？ 既然 $j$ 可以遍历到某个位置停下来，那么可以进一步思考这个

如果我们找到了一个 $height[j] \geq left$ 后，那么只要 $i$ 继续枚举后面的柱子高度满足 $height[i] \leq height[j]$ 的话，那么木桶还是右侧大。

我们如果进一步说，如果我们和 $i$ 一样，$j$ 从后枚举过程中顺带计算出 $j$ 右侧柱子的最大值的话，记为 $right$，那么：

  • 当 $i$ 计算得到的 $left$ 和 $j$ 计算得到的 $right$：$left > right$。此时说明右侧柱子偏低，那么此时，可以让 $j$ 向前移动，因为只要 $left > right$，那么当前 $j$ 位置必然因为 木桶效应，其左侧和右侧最小值是 $right$
  • 同理，如果 $right > left$ 的话，那么让 $i$ 向后移动即可

按照这样的枚举方式，可以实现 $i, j$ 指针都朝着固定方向移动

时间复杂度 - $O(N)$

  • $i, j$ 指针都朝着固定方向移动，因此时间复杂度为 $O(N)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func trap(height []int) int {
    n, res := len(height), 0
    // i 指针从前往后枚举，同时顺带得到left：左侧柱子的最大值
    // j 指针从后往前枚举，同时顺带得到right：右侧柱子的最大值
    for i, j, left, right := 0, n - 1, 0, 0; i < j; {
        left = max(left, height[i]); right = max(right, height[j]);
        // 双指针过程，如果 left <= right，那么将 i 指针向后移动，反之 j 指针向前移动
        if left <= right { 
            res += left - height[i]; i++ 
        } else { 
            res += right - height[j]; j-- 
        }
    }
    return res
}

func min(x, y int) int { if x < y { return x }; return y }
func max(x, y int) int { if x > y { return x }; return y }
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int res = 0;
        for (int i = 0, j = n - 1, left = 0, right = 0; i < j; ) {
            left = max(left, height[i]), right = max(right, height[j]);
            if (left <= right) res += left - height[i++];
            else res += right - height[j--];
        }
        return res;
    }
};

方法 4：单调栈 - $O(N)$

单调栈

由于这个是第一次遇到单调栈，担心一些同学还未学习过单调栈，这里稍微讲解一下单调栈：

  • 单调栈就是一个栈，只是栈里面元素大小关系是单调的：比如从栈底到栈顶，元素按照升序顺序排列

单调栈如何实现？

  • 每次加入一个元素 $x$ 的时候，将栈中所有比当前 $x$ 的大的数都弹出栈
  • 将当前元素 $x$ 入栈

那么单调栈和这个题目的关系是什么呢？

我们观察下图所示，可以知道，每次枚举到一个柱子，其和前面柱子之间，我们 考虑会新增多少水量

  • 我们观察发现，如下图所示，蓝色标识之前柱子可以接到的水
  • 红色和蓝色部分之间就是当前柱子可以使得整体新增的水量

那么我们发现：

  • 当前柱子高度记为 $height[i]$，前面只要存在比其高度小的柱子 $height[j] \leq height[i]$，那么两者之间就会新增一定水量。
  • 当遇到比当前柱子 $height[i]$ 高得柱子 $height[j] > height[i]$ 得时候，就无法继续产生更多得水量了

进一步我们观察发现：

  • 对于当前柱子 $j$: $height[j] \geq height[i]$ 产生的水量是：$(height[j] - height[j - 1]) * (j - i - 1)$
  • 最后一个柱子 $j$： $height[j] > height[i]$ 也会产生一个水量：$(height[i] - height[j - 1]) * (j - i - 1)$

注意： 这里 $height[j - 1]$ 是为了方便表述，应该是单调栈中 $j$ 的下一个柱子

因此，我们每次需要模拟这个过程。和上面讲解的单调栈是完全相同的。

这里可能不容易理解，具体大家可以结合代码一起来看这个过程。

时间复杂度 - $O(N)$

  • 单调栈，每个元素只会入栈和出栈一次，因此时间复杂度为 $O(N)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func trap(height []int) int {
    // stk: 初始化一个空栈
    n, res, stk := len(height), 0, []int{}
    for i := 0; i < n; i++ {
        last := 0
        // 单调栈过程：从栈顶开始看，如果栈顶元素比当前柱子高度低，那么就弹出栈。
        for len(stk) > 0 && height[top(stk)] <= height[i] {
            // 上面讲解了：比当前柱子高度低的柱子，水量计算
            res += (height[top(stk)] - last) * (i - top(stk) - 1)
            last = height[top(stk)]
            stk = stk[:len(stk) - 1]
        }
        // 最后如果存在一个比当前柱子高的柱子，则需要单独计算最后这个柱子增加的水量
        if len(stk) > 0 { res += (height[i] - last) * (i - top(stk) - 1) }
        stk = append(stk, i)
    }
    return res
}

// 返回栈顶元素
func top(stk []int) int { return stk[len(stk) - 1] }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    stack<int> stk;

    int trap(vector<int>& height) {
        int n = height.size();
        int res = 0;
        for (int i = 0; i < n; ++i) {
            int last = 0;
            while (stk.size() && height[stk.top()] <= height[i]) {
                res += (height[stk.top()] - last) * (i - stk.top() - 1);
                last = height[stk.top()];
                stk.pop();
            }
            if (stk.size()) res += (height[i] - last) * (i - stk.top() - 1);
            stk.push(i);
        }
        return res;
    }
};