单调栈 · 矩形面积与接雨水

1. 核心原理

本章讨论的问题模板是：

给一个数组 heights 表示一组连续柱子的高度，求所有柱子组合能围成的最大轴对齐矩形面积。

母题是 LeetCode 84 柱状图中最大的矩形。这一族问题的共同点是：每个矩形都可以由"它最矮的那根柱子"唯一确定——矩形的高度等于该柱子的高度，宽度由它左右两侧第一个比它更矮的柱子约束。

暴力解的瓶颈

枚举每根柱子 i 作为矩形的最矮柱，分别向左、向右扫直到遇到比 heights[i] 矮的柱子为止，记下"左边界" L[i] 和"右边界" R[i]，矩形面积为 heights[i] × (R[i] - L[i] - 1)。单次扫描最坏 O(n)，对全部 i 累计是 O(n²)，空间 O(1)。在 n ≤ 10⁵ 范围下达 10¹⁰ 次操作，超时。

瓶颈仍然是"每个 i 各自从零开始扫描"——上一章已经看到，"对每个 i 找两侧第一个满足条件 P 的下标"是单调栈擅长的题型。

用单调栈一次性获得左右最近更小

引入一个栈，栈中存储下标。不变量：栈中下标对应的高度从栈底到栈顶严格递增。

从左到右扫描 heights。对当前下标 i：

1. 若栈非空且 heights[stack[-1]] ≥ heights[i]，栈顶下标 j 找到了"右侧第一个不严格更高"的位置 i。此时新栈顶（即 j 之前的元素）就是 j 的"左侧第一个严格更矮"的位置 L[j]。
2. 出栈 j 并结算以 heights[j] 为最矮柱的矩形：宽 = i - L[j] - 1，面积 = heights[j] × 宽。
3. 重复，直到栈空或栈顶 < heights[i]，再把 i 入栈。

为简化边界，在栈底放虚拟下标 -1（左哨兵，对应"无左界"），并在数组末尾追加虚拟高度 0（右哨兵，触发把栈中剩余元素全部弹出）。这样每根柱子在退栈时都能算出一个完整的"以它为最矮柱"的矩形面积。

复杂度

每个下标至多入栈一次、出栈一次，外层循环 O(n)、内层 while 摊还 O(n)，总时间 O(n)，空间 O(n)。

这套思想可以推广到一类"贡献法"题型——把"总答案"按"每个元素在何种区间内是最值"分摊到单个元素上。LC 907 子数组最小值之和、LC 1856 子数组最小乘积、LC 42 接雨水都属于这一族。

2. 通用模板

下面给出 LC 84 的一遍扫紧凑写法，包含左右哨兵处理。这份骨架同样适用于"求所有矩形最大面积"的派生题，只需修改结算公式。

def largest_rectangle(heights: list[int]) -> int:
    """
    单调严格递增栈，存下标。
    当 heights[i] ≤ heights[stack[-1]] 时弹出栈顶 j，
    此时 L[j] = 新栈顶，R[j] = i，宽 = i - L[j] - 1。
    """
    n = len(heights)
    stack = [-1]                                # 左哨兵：无左界时 L = -1
    ans = 0
    for i in range(n + 1):
        h = heights[i] if i < n else 0          # 右哨兵：尾部追加高度 0 触发清空
        while stack[-1] != -1 and heights[stack[-1]] >= h:
            j = stack.pop()                     # 以 heights[j] 为最矮柱结算
            width = i - stack[-1] - 1           # 新栈顶即 L[j]
            ans = max(ans, heights[j] * width)
        stack.append(i)
    return ans

public int largestRectangle(int[] heights) {
    int n = heights.length;
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(-1);                              // 左哨兵：无左界时 L = -1
    int ans = 0;
    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];       // 右哨兵：尾部追加高度 0
        while (stack.peek() != -1 && heights[stack.peek()] >= h) {
            int j = stack.pop();                 // 以 heights[j] 为最矮柱结算
            int width = i - stack.peek() - 1;    // 新栈顶即 L[j]
            ans = Math.max(ans, heights[j] * width);
        }
        stack.push(i);
    }
    return ans;
}

int largestRectangle(vector<int>& heights) {
    int n = (int) heights.size();
    stack<int> st;
    st.push(-1);                                 // 左哨兵：无左界时 L = -1
    int ans = 0;
    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];       // 右哨兵：尾部追加高度 0
        while (st.top() != -1 && heights[st.top()] >= h) {
            int j = st.top();                    // 以 heights[j] 为最矮柱结算
            st.pop();
            int width = i - st.top() - 1;        // 新栈顶即 L[j]
            ans = max(ans, heights[j] * width);
        }
        st.push(i);
    }
    return ans;
}

模板上有四处需要明确：

• pop 条件 >= 而非 >：遇到相等高度时直接弹出，是为了让相等的柱子在同一轮被合并处理。即便较早一根被以"过窄宽度"结算，相等组中最右那根仍留在栈里，最终能给出最大宽度。两种写法在最优面积上等价，>= 代码更简洁。
• 左哨兵 -1：栈底放 -1，当某根柱子的 L[j] 不存在时，新栈顶就是 -1，宽度公式 i - (-1) - 1 = i 自然成立，避免额外判空。
• 右哨兵高度 0：循环写到 i == n 时强制取 h = 0，触发把栈中剩余所有下标弹出结算，这样写就不必在循环外再来一段"扫描结束后处理剩余栈"的代码。
• 宽度 = i - L[j] - 1：以 heights[j] 为最矮柱的矩形横跨开区间 (L[j], i)，长度为 i - L[j] - 1。+1 或 -1 的错位是这一族题最常见的实现错误，可以用 [2, 1, 2] 这种最短样例验证。

两遍扫的等价写法

模板里"边走边结算"是一遍扫紧凑版。等价的两遍扫写法更直观：第一遍正向扫单调栈得到每个 i 的 L[i]，第二遍反向扫得到 R[i]，再统一计算面积。代码分了三步，调试时各步可独立验证；面试白板上若担心一遍扫的"被 pop 时双边界都已知"想不清楚，写两遍扫亦可。两种写法时间均为 O(n)，常数因子上一遍扫略优。

3. 母题精讲

LeetCode 84 柱状图中最大的矩形

链接：LeetCode 84

题意：给一个整数数组 heights，每个 heights[i] 表示一个宽度为 1 的柱子的高度。所有柱子并排站在 x 轴上。求所有柱子组合可以围成的最大矩形面积——矩形必须紧贴 x 轴，宽度是连续若干根柱子。

数据范围：

• heights.length：1 到 10⁵
• heights[i]：0 到 10⁴

示例：

输入：heights = [2, 1, 5, 6, 2, 3]
输出：10
解释：最大矩形是高度 5、宽度 2 的方块（柱 2 和柱 3 一起），面积 5 × 2 = 10。

暴力解：枚举每根柱子作为最低柱

对每根柱子 i，看它能向左、向右各扩展多远——只要继续扩展的柱子高度仍 ≥ heights[i]，矩形高度就还是 heights[i]。一旦碰到比它矮的，扩展就停。这样每个 i 能给出一个候选答案 heights[i] × 宽度：

class Solution:
    def largestRectangleArea_brute(self, heights: list[int]) -> int:
        n = len(heights)
        ans = 0
        for i in range(n):
            # 向左找第一个比 heights[i] 小的位置
            l = i - 1
            while l >= 0 and heights[l] >= heights[i]:
                l -= 1
            # 向右找第一个比 heights[i] 小的位置
            r = i + 1
            while r < n and heights[r] >= heights[i]:
                r += 1
            # 宽度是 (l, r) 开区间，即 r - l - 1
            ans = max(ans, heights[i] * (r - l - 1))
        return ans

时间 O(n²)，空间 O(1)。n ≤ 10⁵ 下最坏 10¹⁰ 次操作，秒级 TLE。例如 heights = [1, 1, 1, ..., 1] 长度 10⁵ 的全 1 数组，每个 i 都要扫遍全数组。

关键观察：所有的"向左找第一个更小"可以一次性算出来

暴力的低效之处在于：每个 i 的"向左找第一个更小元素"都是独立从头扫。但其实这件事在整个数组上是一个整体结构——上一章 下一个更大元素 讲过，对每个 i 找右边第一个满足某条件的下标，单调栈能在 O(n) 内一次算完。

这里要找的是"左/右第一个比 heights[i] 严格小的下标"。把这两组下标一次性算出来后，每根柱子的最大矩形宽度就是 right_smaller[i] - left_smaller[i] - 1，对所有 i 取最大即可。

下面这个交互演示走一遍 [2, 1, 5, 6, 2, 3] 上的单调栈过程，标出每根柱子的左右扩展边界：

最终 ans = 10。注意几个工程上的关键点：栈底加哨兵 -1 避免"left 不存在"的边界判断；数组末尾的"虚拟 0"触发剩余 pop。下面进入例题。

4. 例题（三道）

下面三道按"维度递增"排：一维直方图 → 二维 0/1 矩阵 → 一维但反向问"凹陷接水"。每道带 follow-up 续到下一题。

4.1 LC 84 柱状图中最大的矩形

回到本章开头那道题。代码就是上面模板的直接应用，复杂度 O(n) 时间、O(n) 空间（栈最坏存 n+1 个下标）。

复杂度从 O(n²) 降到 O(n)。n = 10⁵ 时从约 10¹⁰ 次操作降到 10⁵，从超时变成毫秒级通过。

Follow-up：把题目从一维数组扩展到二维 0/1 矩阵——求矩阵里只含 1 的最大矩形面积。能不能用 LC 84 的解法当子过程？

4.2 LC 85 最大矩形

链接：LeetCode 85

题意：给一个 m × n 的 0/1 字符矩阵 matrix（元素是字符 '0' 或 '1'）。求矩阵里只含 1 的最大矩形面积。

数据范围：

• m, n：1 到 200
• matrix[i][j]：字符 '0' 或 '1'

示例：

输入：matrix = [
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
输出：6
解释：第 2 行（0-indexed）和第 3 行中间那块 2×3 的全 1 矩形最大。

思路：把每一行视为"以这一行为底的直方图"。具体说，对每一行 r，计算一个数组 height[r]——其中 height[r][j] 是从位置 (r, j) 向上数（含自身）连续 1 的个数。如果 matrix[r][j] = '0'，height[r][j] = 0。

原矩阵                  height 矩阵
1 0 1 0 0              1 0 1 0 0
1 0 1 1 1              2 0 2 1 1
1 1 1 1 1              3 1 3 2 2     ← 这一行的直方图 [3,1,3,2,2] 跑 LC 84 → 答案 6
1 0 0 1 0              4 0 0 3 0

现在对每一行的 height[r] 跑一遍 LC 84 的"直方图最大矩形"，取所有行的最大值就是答案。

class Solution:
    def maximalRectangle(self, matrix: list[list[str]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        m, n = len(matrix), len(matrix[0])
        height = [0] * n                       # 持续累加的"高度数组"
        ans = 0

        def largest_rectangle(heights):        # LC 84 子过程
            stack = [-1]
            best = 0
            for i in range(len(heights) + 1):
                h = heights[i] if i < len(heights) else 0
                while stack[-1] != -1 and heights[stack[-1]] >= h:
                    j = stack.pop()
                    best = max(best, heights[j] * (i - stack[-1] - 1))
                stack.append(i)
            return best

        for r in range(m):
            for j in range(n):
                if matrix[r][j] == '1':
                    height[j] += 1
                else:
                    height[j] = 0              # 0 切断累计
            ans = max(ans, largest_rectangle(height))
        return ans

复杂度：每一行 O(n) 跑直方图，总 O(m × n)。m, n ≤ 200 下 4 × 10⁴ 次操作，毫秒级。

注意 height[j] = 0 是关键——遇到 0 必须把累计断掉，否则后续行的"向上连续 1"就算错了。

Follow-up：上面两题都是求"装满某段连续高度的最大矩形"。如果反过来——给一组柱子，问相邻柱子之间凹下去的部分能接多少雨水呢？

4.3 LC 42 接雨水

链接：LeetCode 42

题意：给一个非负整数数组 height 表示一组柱子的高度，所有柱子宽度都是 1。如果在这些柱子上下雨，求能接住多少雨水（每一格单位）。

数据范围：

• n：1 到 2 × 10⁴
• height[i]：0 到 10⁵

示例：

输入：height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
输出：6
解释：图示中黑色是柱子，蓝色是接住的雨水：

      |
  |   ||  |
__|_||||_||__
6 格雨水

这道题有三种主流解法（双指针、动态规划、单调栈），都是 O(n)。这里主讲单调栈解法——和 LC 84/85 共享单调栈骨架；面试常被追问"能不能做到 O(1) 额外空间"——答案就是双指针，附在末尾对照。

单调栈解法的核心：从左到右扫，维护一个单调递减栈（栈底到栈顶高度递减）。当 height[i] 大于栈顶时，pop 出一个"坑底" j，此时栈顶（新的 top）是 j 的"左壁" l，i 是"右壁" r。这一层雨水的累积 = (min(height[l], height[r]) - height[j]) × (r - l - 1)——左右壁较低的那个减去坑底高度，再乘宽度。

class Solution:
    def trap(self, height: list[int]) -> int:
        n = len(height)
        stack = []                             # 存下标，对应高度严格递减
        water = 0
        for i in range(n):
            while stack and height[stack[-1]] < height[i]:
                j = stack.pop()                # 当前坑底
                if not stack:
                    break                      # 没有左壁，凑不出"坑"
                l = stack[-1]                  # 左壁
                left_h, right_h = height[l], height[i]
                water += (min(left_h, right_h) - height[j]) * (i - l - 1)
            stack.append(i)
        return water

复杂度：每个下标至多 push 一次、pop 一次，总 O(n) 时间、O(n) 空间。

需要小心的是 if not stack: break 这一句——pop 后栈空意味着没有左壁，比如 height = [3, 0, 0] 中扫到 i=0 时栈空，没法接水。

为什么单调栈解法对：每次 pop 出的 j 是当前"坑底"，它的左边在栈里立刻就是它的"左边第一个更高柱"（因为栈递减），它的右边正好是 i（因为 height[i] 比 height[j] 高才触发了 pop）。所以 j 这一格被两侧的更高柱子精确"包夹"，能接的水量就是上面那个公式。

每个下标只贡献一层水，所以分摊下来 O(n)。单调栈在这里把原本看起来非局部的"接水量"拆成每个坑底的局部贡献。

双指针解法（O(1) 空间）

面试官常追问"O(n) 空间能不能压到 O(1)"——可以，用双指针：

def trap_two_pointer(height: list[int]) -> int:
    if not height:
        return 0
    l, r = 0, len(height) - 1
    left_max, right_max = 0, 0
    ans = 0
    while l < r:
        if height[l] < height[r]:
            # 左边较矮，左壁是 left_max，坑底是 height[l]
            left_max = max(left_max, height[l])
            ans += left_max - height[l]
            l += 1
        else:
            right_max = max(right_max, height[r])
            ans += right_max - height[r]
            r -= 1
    return ans

不变量：height[l] < height[r] 时，left_max 一定不超过 right_max，所以 l 这一格的"两侧较低壁" = left_max；反过来同理。每轮 l/r 至少一个推进，O(n) 时间、O(1) 空间。

面试场景下：单调栈解法体现"统一套路、跨题复用"的能力，双指针解法体现"针对此题做空间优化"的能力——两者都值得熟练，单调栈优先讲，双指针作为 follow-up 回答。

5. 边界、易错与复杂度

pop 条件 >= vs >

LC 84 / 85 用 >=：相等高度互相 pop 也没事，最右那根会保留并最终给出最优。这是少数 >= 能简化代码的场景。

LC 42 用 <（严格递减栈）：相等高度的柱子之间接不了水（同一水平面），让它们顶替而不互相 pop。

哨兵 -1 / 末尾 0 的作用

LC 84 用了两个哨兵——左哨兵 -1 避免 L[i] 不存在 时取空栈；右哨兵（数组末尾的 0）触发栈里剩余元素的 pop。少了哨兵也能写对，但代码里会多几个 if stack: 判断。哨兵让模板更干净。

LC 42 不需要末尾 0——栈里剩下的柱子单调递减，本来就接不到右边的水，自然丢弃。

单调栈解法的复杂度严格证明

每个下标 i：

• push 1 次（每轮循环显式 push）
• pop ≤ 1 次（while 里弹出，一旦弹出就再也不回来）

总操作 ≤ 2n + 哨兵开销，所以 O(n)。这套摊还分析跟 上一章 完全一样。

当题目给的是矩阵时

矩阵题（LC 85）的标准玩法是"逐行做直方图 + 套 LC 84"。复杂度 O(m × n)，比"枚举所有左上右下角"的 O(m² × n²) 快得多。

类似的玩法还有 LC 1504（统计全 1 子矩形），用"逐行直方图 + 单调栈贡献法"也能 O(m × n) 解。

复杂度速查

7. 小结

单调栈在这一章被推到了贡献法的高度——不是简单地"找下一个 X"，而是把每个元素对总答案的贡献按"它在什么区间里是最值"分摊出来。LC 84 / 85 / 42 / 907 / 1856 都是这一族。

记住三个关键工具：

• 哨兵 -1 和末尾 0：简化 LC 84 模板的边界判断
• 左严格 / 右非严格：贡献法处理重复值时避免双重计数（LC 907 / 1856）
• 双单调栈：处理"第二次更大"这种需要"先存起来再触发"的题（LC 2454）

下一章预告——单调栈系列的第三个方向是字典序问题：LC 402 移掉 K 位数字、LC 316 去除重复字母让结果最小、LC 321 拼接两数组使结果最大。这些题用单调栈 + 贪心维护"目前能给出的最小/最大字典序前缀"，是另一类完全不同的应用模式。

对应灵神题单：矩形面积 / 接雨水 / 贡献法 / 单调栈优化 DP

进一步阅读：灵茶山艾府《单调栈题单》第二、三部分；LeetCode 单调栈标签 下的高频题