第3章｜栈与队列

Unit 09 · 弹栈时确定矩形左右边界

← Unit 08
U09
Largest RectangleBoundary · Width · Monotonic Stack

柱子留在栈里，不是因为答案未知，
而是它的右边界还没有出现。

一个柱子能够向两侧扩展多远，取决于左右第一个更矮柱。向右扫描时，当前更矮柱第一次封住栈顶的右侧；弹栈后的新栈顶则暴露左侧更矮边界。此刻矩形宽度才完整确定。

LeetCode #84 题目模型以每根柱高为矩形最矮高度，寻找最大可扩展宽度

题目要求

给定非负整数数组 heights，每个元素表示宽度为 1 的柱子高度。选择一段连续柱子形成矩形，矩形高度不能超过区间内最矮柱，返回能够形成的最大矩形面积。

from typing import List class Solution: def largestRectangleArea( self, heights: List[int] ) -> int: pass

输入、输出与复杂度目标

  • 输入：柱高数组；输出：最大矩形面积；
  • 目标时间复杂度：O(n)；
  • 额外空间复杂度：O(n)。

示例

输入：heights = [2,1,5,6,2,3]
输出：10
解释：高度 5 和 6 组成宽度 2、高度 5 的矩形。
输入：heights = [2,4]
输出：4

数据约束

  • 1 ≤ heights.length ≤ 10⁵
  • 0 ≤ heights[i] ≤ 10⁴
  • 矩形必须覆盖连续柱子，每根柱宽固定为 1。
Limiting Height

某根柱作为矩形最矮高度时，面积由该高度与可扩展宽度决定。

First Smaller

左右第一个更矮柱负责截断矩形；边界柱本身不计入宽度。

Monotonic Stack

栈保存尚未遇到右侧更矮柱的索引，高度从栈底到栈顶单调不减。

Resolve on Pop

弹栈时右边界是当前索引，左边界是弹栈后的新栈顶。

Unit 08 · #739 每日温度当前更高温度到达时，历史索引出栈，答案是“等待距离”。
→
Unit 09 · #84 柱状图最大矩形当前更矮柱到达时，历史索引出栈，答案升级为“左右边界之间的面积”。
认知任务 1
高度 5 的柱子能与右侧高度 6 的柱子组成多大矩形？
矩形高度由区间内最矮柱决定；宽度等于连续柱子数量。
主动画区人工矩形模式
heights = [2,1,5,6,2,3]当前候选：以高度 5 为最矮柱

未封闭柱子栈 保存 extended 中的索引

弹栈结算面板 边界柱不计入宽度

被弹出索引—
矩形高度—
左侧更矮边界—
右侧更矮边界—
有效宽度—
本次面积—
当前最大面积 max_area0
width = right - left - 1
选择高度 5 与 6 的连续区间。
比较次数0
入栈次数0
出栈次数0
面积结算0

累计工作量

Read
Compare Top
Pop Height
Find Bounds
Compute Area
Push / Finish
回答当前问题后继续

关键代码补全

from typing import List
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
extended =
stack = [0]
max_area = 0
for right in range(1, len(extended)):
while :
height = extended[stack.pop()]
width =
max_area = max(max_area, )
stack.append()
return max_area
提示 1：先把边界情况编译进数据。 extended = [0] + heights + [0] 提示 2：只有当前柱严格更矮时，栈顶柱的右边界才出现。 extended[stack[-1]] > extended[right] 提示 3：必须先 pop，再读取新的 stack[-1] 作为左侧更矮边界。 width = right - stack[-1] - 1 提示 4：每次弹栈只结算一个“以该柱高为限制高度”的最大矩形。
另一种写法可使用哨兵索引 -1 与末尾高度 0。主动画采用双哨兵，是为了让左右边界在画面中都有明确位置。

代码与图像逐行联动

1from typing import List
3class Solution:
4 def largestRectangleArea(...):
5 extended = [0] + heights + [0]
6 stack = [0]
7 max_area = 0
9 for right in range(1, len(extended)):
10 while extended[stack[-1]] > extended[right]:
11 height = extended[stack.pop()]
12 width = right - stack[-1] - 1
13 max_area = max(max_area, height * width)
14 stack.append(right)
16 return max_area
right / current height—
stack indices[0]
popped / height—
left / right—
width / area—
max_area0
轨迹将扫描左右哨兵之间的全部柱子，并在每次弹栈时同步展示边界和面积。
完成代码联动后进入 LeetCode #85 官方原题迁移代码补全正确或播放完整轨迹后解锁。

迁移题：LeetCode #85「最大矩形」

这不是简单地“对每一行调用一次 #84”。迁移的关键是先证明二维矩形可以按其底边所在行，唯一转换为一张柱状图；随后再复用 #84 的边界算法。

1 认识官方原题
2 对照二维与一维
3 映射状态语义
4 运行官方样例

第一步：先完整理解 #85 原题，再谈复用 #84

官方题意与函数签名

给定一个只包含字符 "0" 和 "1" 的二维矩阵，寻找只由 "1" 组成的最大轴对齐矩形，并返回面积。

from typing import List class Solution: def maximalRectangle( self, matrix: List[List[str]] ) -> int: pass
LeetCode 官方题面 ↗
官方样例与约束
matrix = [["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"]] 输出：6
  • 1 ≤ rows, cols ≤ 200；
  • 每个单元格是字符 "0" 或 "1"；
  • 返回的是一个整数面积，不是矩形坐标；
  • 矩形只能包含连续行、连续列，并且所有格子都必须为 "1"。
读题检查 1：官方函数最终返回什么？
先区分“中间表示”和“最终输出”。
读题检查 2：某列当前行为 "0" 时，高度应如何更新？
柱高表示“以当前行为底边的连续 1 数量”。
完成两道读题检查后进入结构对照。

第二步：#85 为什么可以复用 #84？

固定某一行作为矩形底边后，每一列向上连续出现的 1 数量就是柱高。任何底边位于该行的全 1 矩形，都与这张柱状图中的某个连续矩形一一对应。

比较维度
#84 柱状图最大矩形
#85 最大矩形
输入状态
一维 heights
二维字符矩阵 matrix
限制高度
区间内最矮柱
以当前行为底边、每列向上连续 1 的高度
边界计算
单调栈寻找左右第一个更矮柱
完全复用 #84，不重新发明二维边界算法
新增状态
无
跨行维护 heights，遇 0 必须归零
答案聚合
返回一张柱状图的最大面积
取所有行柱状图最大面积的最大值
结构检查：为什么处理完第 2 行后得到的 heights 能表示“底边在第 2 行”的所有候选矩形？
二维矩形的高度必须在所有覆盖列上连续成立。
- 输入已经是一维 heights
+ 初始化 heights = [0] * cols
+ 对每一行更新：1 → 累加，0 → 归零
+ row_area = largest_histogram(heights)
+ answer = max(answer, row_area)

  #84 的单调栈核心保持不变：
  while extended[stack[-1]] > extended[right]:
      height = extended[stack.pop()]
      width = right - stack[-1] - 1
完成结构检查后进入语义槽位。

第三步：不要背整段答案，先映射四个新增语义

#84 的辅助函数可以原样复用。你只需要确定二维包装层新增的四个状态变化。

槽位 A · 列状态初始化

每一列初始都没有连续的 1。

槽位 B · 当前行更新

1 延长连续高度，0 截断并归零。

槽位 C · 一维问题复用

每一行更新后，立刻计算以该行为底边的最佳矩形。

槽位 D · 跨行聚合

全局答案必须保留此前所有底边行中的最大值。

class Solution:
    def maximalRectangle(self, matrix):
        if not matrix:
            return 0

        # 完成四个语义槽位后生成包装层
        ...
# 表示不变量
处理 row 之后：

heights[c]
= 以当前 row 为底边，
  第 c 列向上连续 1 的数量

answer
= 已处理所有行中，
  最大全 1 矩形面积
四个槽位全部正确后运行官方样例。

第四步：逐行运行官方样例，验证“二维压缩 + #84 复用”

官方矩阵
当前行压缩后的柱状图
当前行尚未开始
heights[0, 0, 0, 0, 0]
本行柱状图最大面积0
全局 answer0
点击“处理下一行”，观察字符 0 如何重置柱高，以及第 2 行如何得到官方答案 6。
可选挑战：独立写出完整 #85 解法

Unit 09 Skill 卡

先把二维问题按“矩形底边所在行”分解。每处理一行，用列高度描述向上连续的 1，再把该行转换为一张柱状图；#84 的单调栈负责求当前底边下的最大矩形，外层循环负责跨行取最大值。

题号 / 主方法#84 · 单调栈边界结算
迁移原题#85 · 二维矩阵逐行压缩
新增状态heights[c] = 向上连续 1 的数量
核心复用每行调用一次 largest_histogram
关键边界字符 "0" 必须把对应列高归零
复杂度时间 O(rows × cols)，空间 O(cols)
常见错误0 不归零；只处理最后一行；把面积相加
方法论固定一维边界，把高维状态压缩成已解决子问题
推荐下一题#239 滑动窗口最大值