2026-06-27
#42 单调栈 困难

接雨水

在 LeetCode 上查看 ↗

🎧 语音讲解

开车或通勤时可听，跟着思路走一遍

速度

📋 题目描述

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

示例 1

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

💭 模拟答题者思考

1. 问题本质：每根柱子能接多少水 = min(左边最高, 右边最高) - 自身高度。

2. 双指针法（按列算）：维护 leftMax / rightMax，谁小就处理谁那侧的柱子。

3. 单调栈法（按行算）：遇到一个上升的柱子，它和左侧柱子形成的「凹槽」可以存水。

4. 每次弹出时，以 mid 为底，left 和 i 为两壁，高度差 × 宽度就是这层的水量。

🧠 变量语义（先读这三句再编码）

变量类型语义（三句法）
ststack<int>定义：存下标，栈内高度单调递减
维护：栈底到栈顶对应的高度严格递减
更新：当前高度 >= 栈顶高度时弹出栈顶并结算雨水；然后将当前下标压入
midint定义：被弹出的低谷位置（即栈顶）
维护：每次弹出时取值
更新：st.pop() 得到
leftint定义：弹出后新栈顶，作为接雨水的左边界
维护：mid 弹出后 st.top()（若栈非空）
更新：结算宽度 = i - left - 1

⌨️ 落码步骤

1. 初始化空栈 st，ans = 0

2. 遍历 height，当前高度 >= 栈顶高度时循环结算

3. mid = st.pop()（谷底），若栈非空则 left = st[-1]

4. h = min(height[left], height[i]) - height[mid]，w = i - left - 1

5. ans += h * w，最后 st.append(i)

💻 代码实现 

class Solution:
    def trap(self, height: list[int]) -> int:
        st = []  # 单调递减栈，存下标
        ans = 0

        for i in range(len(height)):
            while st and height[i] >= height[st[-1]]:
                mid = st.pop()
                if not st:
                    break
                left = st[-1]
                h = min(height[left], height[i]) - height[mid]
                w = i - left - 1
                ans += h * w
            st.append(i)

        return ans

# 双指针优化版（O(1) 空间）：
class Solution:
    def trap(self, height: list[int]) -> int:
        l, r = 0, len(height) - 1
        left_max = right_max = 0
        ans = 0
        while l < r:
            left_max = max(left_max, height[l])
            right_max = max(right_max, height[r])
            if left_max < right_max:
                ans += left_max - height[l]
                l += 1
            else:
                ans += right_max - height[r]
                r -= 1
        return ans
class Solution {
public:
    int trap(vector& height) {
        stack st;  // 单调递减栈，存下标
        int ans = 0;

        for (int i = 0; i < height.size(); i++) {
            while (!st.empty() && height[i] >= height[st.top()]) {
                int mid = st.top(); st.pop();
                if (st.empty()) break;
                int left = st.top();
                int h = min(height[left], height[i]) - height[mid];
                int w = i - left - 1;
                ans += h * w;
            }
            st.push(i);
        }
        return ans;
    }
};
// 时间 O(n)，空间 O(n)
// 双指针优化版可达 O(1) 空间

📈 复杂度分析

时间复杂度 O(n)
空间复杂度 O(n)

⚠️ 常见坑

❗ 单调栈要求 height[i] >= height[st[-1]]（而非 >）：相等时也要弹出，否则会重复计算。

❗ 弹出 mid 后栈为空：说明当前柱子高过所有左侧柱，无法形成凹槽，直接 break。

❗ 双指针法只适用于算「每列能接多少」，单调栈法算「每行（水平层）能接多少」——两种思路完全不同。

🔍 必测边界 Case

Case 1：单调递增
height = [1,2,3,4] → 输出 0（无凹槽）
Case 2：V 形
height = [3,0,3] → 输出 3
Case 3：空数组
height = [] → 输出 0