题目链接 · 灵神原题解（署名来源）

视频讲解

请看【基础算法精讲 02】，欢迎点赞关注~

方法一：前后缀分解

注：计算 $\mathit{\text{preMax}}$ 的循环和计算 $\mathit{\text{ans}}$ 的循环，可以合并成一个循环。这里为了方便大家阅读，没有合并。

Python 解法1

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        pre_max = [0] * n  # pre_max[i] 表示从 height[0] 到 height[i] 的最大值
        pre_max[0] = height[0]
        for i in range(1, n):
            pre_max[i] = max(pre_max[i - 1], height[i])

        suf_max = [0] * n  # suf_max[i] 表示从 height[i] 到 height[n-1] 的最大值
        suf_max[-1] = height[-1]
        for i in range(n - 2, -1, -1):
            suf_max[i] = max(suf_max[i + 1], height[i])

        ans = 0
        for h, pre, suf in zip(height, pre_max, suf_max):
            ans += min(pre, suf) - h  # 累加每个水桶能接多少水
        return ans

C++ 解法1

// C++ 版待补充

C++ 解法2

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> pre_max(n); // pre_max[i] 表示从 height[0] 到 height[i] 的最大值
        pre_max[0] = height[0];
        for (int i = 1; i < n; i++) {
            pre_max[i] = max(pre_max[i - 1], height[i]);
        }

        vector<int> suf_max(n); // suf_max[i] 表示从 height[i] 到 height[n-1] 的最大值
        suf_max[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            suf_max[i] = max(suf_max[i + 1], height[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += min(pre_max[i], suf_max[i]) - height[i]; // 累加每个水桶能接多少水
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\mathit{\text{height}}$ 的长度。
• 空间复杂度：$\mathcal{O}(n)$。

方法二：相向双指针（一次遍历）

设现在算出了前缀 $[0,\mathit{\text{left}}]$ 的最大高度 $\mathit{\text{preMax}}[\mathit{\text{left}}]$，以及后缀 $[\mathit{\text{right}},n-1]$ 的最大高度 $\mathit{\text{sufMax}}[\mathit{\text{right}}]$。中间的柱子 $[\mathit{\text{left}}+1,\mathit{\text{right}}-1]$ 尚未遍历，不知道有多高。在这种情况下，我们能否直接确定 $\mathit{\text{left}}$ 或者 $\mathit{\text{right}}$ 处的接水量？

分类讨论：

• 如果 $\mathit{\text{preMax}}[\mathit{\text{left}}]\le \mathit{\text{sufMax}}[\mathit{\text{right}}]$，由于 $\mathit{\text{sufMax}}[\mathit{\text{right}}]\le \mathit{\text{sufMax}}[\mathit{\text{left}}]$（包含的数越多，最大值越大），所以 $\mathit{\text{preMax}}[\mathit{\text{left}}]\le \mathit{\text{sufMax}}[\mathit{\text{right}}]\le \mathit{\text{sufMax}}[\mathit{\text{left}}]$，所以 $min(\mathit{\text{preMax}}[\mathit{\text{left}}],\mathit{\text{sufMax}}[\mathit{\text{left}}])=\mathit{\text{preMax}}[\mathit{\text{left}}]$，$\mathit{\text{left}}$ 处的接水量就是 $\mathit{\text{preMax}}[\mathit{\text{left}}]-\mathit{\text{height}}[\mathit{\text{left}}]$。
• 如果 $\mathit{\text{preMax}}[\mathit{\text{left}}]\ge \mathit{\text{sufMax}}[\mathit{\text{right}}]$，由于 $\mathit{\text{preMax}}[\mathit{\text{left}}]\le \mathit{\text{preMax}}[\mathit{\text{right}}]$（包含的数越多，最大值越大），所以 $\mathit{\text{sufMax}}[\mathit{\text{right}}]\le \mathit{\text{preMax}}[\mathit{\text{left}}]\le \mathit{\text{preMax}}[\mathit{\text{right}}]$，所以 $min(\mathit{\text{preMax}}[\mathit{\text{right}}],\mathit{\text{sufMax}}[\mathit{\text{right}}])=\mathit{\text{sufMax}}[\mathit{\text{right}}]$，$\mathit{\text{right}}$ 处的接水量就是 $\mathit{\text{sufMax}}[\mathit{\text{right}}]-\mathit{\text{height}}[\mathit{\text{right}}]$。

这意味着，在没有遍历完 $\mathit{\text{height}}$ 数组的情况下，也能算出接水量。这引出了如下相向双指针（一次遍历）做法。

注：代码实现时，$\mathtt{\text{while}}$ 循环可以不加等号。因为在「谁小移动谁」的规则下，相遇的位置一定是最高的柱子，这个柱子是无法接水的。

Python 解法3

class Solution:
    def trap(self, height: List[int]) -> int:
        ans = pre_max = suf_max = 0
        left, right = 0, len(height) - 1
        while left < right:
            pre_max = max(pre_max, height[left])  # 前缀最大值
            suf_max = max(suf_max, height[right])  # 后缀最大值
            if pre_max < suf_max:  # 可以确定 left 处的接水量
                ans += pre_max - height[left]
                left += 1  # 搞定了 left，现在问题缩小到 [left+1, right]
            else:  # 可以确定 right 处的接水量
                ans += suf_max - height[right]
                right -= 1  # 搞定了 right，现在问题缩小到 [left, right-1]
        return ans

C++ 解法3

// C++ 版待补充

C++ 解法4

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        int pre_max = 0, suf_max = 0;
        int left = 0, right = height.size() - 1;
        while (left < right) {
            pre_max = max(pre_max, height[left]); // 前缀最大值
            suf_max = max(suf_max, height[right]); // 后缀最大值
            if (pre_max < suf_max) { // 可以确定 left 处的接水量
                ans += pre_max - height[left];
                left++; // 搞定了 left，现在问题缩小到 [left+1, right]
            } else { // 可以确定 right 处的接水量
                ans += suf_max - height[right];
                right--; // 搞定了 right，现在问题缩小到 [left, right-1]
            }
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\mathit{\text{height}}$ 的长度。
• 空间复杂度：$\mathcal{O}(1)$。

方法三：单调栈

请看 单调栈【基础算法精讲 26】。

上面的方法相当于「竖着」计算面积，单调栈的做法相当于「横着」计算面积。

这个方法可以总结成 $16$ 个字：找上一个更大元素，在找的过程中填坑。

注意 $\mathtt{\text{while}}$ 中加了等号，这可以让栈中没有重复元素，从而在有很多重复元素的情况下，使用更少的空间。

点评：看复杂度的话，单调栈不如双指针的做法。但如果输入的 $\mathit{\text{height}}$ 是一个流（stream），只能从左到右遍历，那么单调栈（在这种场景下）就是不错的方法了。

Python 解法5

class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        st = []
        for i, h in enumerate(height):
            while st and height[st[-1]] <= h:
                bottom_h = height[st.pop()]
                if not st:  # 栈是空的
                    break
                left = st[-1]
                dh = min(height[left], h) - bottom_h  # 面积的高
                ans += dh * (i - left - 1)
            st.append(i)
        return ans

C++ 解法5

// C++ 版待补充

C++ 解法6

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        stack<int> st;
        for (int i = 0; i < height.size(); i++) {
            int h = height[i];
            while (!st.empty() && height[st.top()] <= h) {
                int bottom_h = height[st.top()];
                st.pop();
                if (st.empty()) {
                    break;
                }
                int left = st.top();
                int dh = min(height[left], height[i]) - bottom_h; // 面积的高
                ans += dh * (i - left - 1);
            }
            st.push(i);
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\mathit{\text{height}}$ 的长度。虽然我们写了个二重循环，但站在每个元素的视角看，这个元素在二重循环中最多入栈出栈各一次，因此循环次数之和是 $\mathcal{O}(n)$，所以时间复杂度是 $\mathcal{O}(n)$。
• 空间复杂度：$\mathcal{O}(min(n,U))$，其中 $U=max(\mathit{\text{height}})-min(\mathit{\text{height}})+1$。注意栈中没有重复元素，在 $\mathit{\text{height}}$ 值域很小的情况下，空间复杂度主要取决于 $\mathit{\text{height}}$ 的值域范围。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府