题目描述
思路解析
一句话答案：LeetCode 85 最大矩形的标准解法是逐行转化成柱状图：用 heights[c] 记录第 c 列到当前行为止连续 1 的个数（遇 0 清零），把每一行当作底、对 heights 跑一遍 LeetCode 84 柱状图最大矩形的单调栈，所有行的结果取最大。时间 O(R×C)、空间 O(C)。
最大矩形这道题在问什么
给一个每格是 0 或 1 的矩阵，要框出一块全部由 1 组成的矩形，让面积最大。直接在二维里暴力枚举矩形，左右上下四条边随便组合就是 O(R²C²) 个候选，每个还要验证内部全 1，完全不可行。这题的价值就在于那一步降维转化。
为什么二维矩阵能压成柱状图
关键观察：任何一块全 1 矩形都有一条确定的底边，落在某一行上。反过来，固定「以第 r 行为底」之后，矩形在每一列能长多高，受限于该列从第 r 行向上连续 1 的个数——把这个数看成柱子的高度，第 r 行为底的所有全 1 矩形，恰好对应这排柱子构成的柱状图里的矩形。
于是原问题被拆成 R 个子问题：每一行作底生成一张柱状图，求柱状图最大矩形（这正是 LeetCode 84），所有行的答案取最大。因为每块矩形都有底行，逐行枚举不会漏掉任何候选。
heights 数组为什么遇 1 加一、遇 0 清零
heights[c] 的定义是：以当前行为底，第 c 列向上数连续 1 的个数。从上一行推到这一行只需一步增量更新：当前格是 1，柱子接着长高，heights[c] 加 1；当前格是 0，这一列被拦腰斩断，heights[c] 必须清零——0 上方那些 1 与本行不连通，不能参与以本行为底的矩形。清零这刀不砍，柱高虚高，答案就会把断开的区域误算进去。增量维护让每行的柱状图只花 O(C) 就能建好，不必每行都从头向上数。
每一行的柱状图怎么用单调栈结算
行内就是标准的 LeetCode 84 解法：维护柱高递增的栈（存下标），当前柱比栈顶矮时弹出栈顶结算——以它为高，宽度是当前下标与弹出后新栈顶之间的格数 i - left - 1，即左右两侧第一根更矮柱夹出的范围；末尾追加一根高 0 的哨兵柱，把扫完后还留在栈里的柱子全部逼出来结算。以题目的 4×5 示例矩阵为例，答案 6 出现在以第 2 行为底的柱状图 [3,1,3,2,2] 里：高 2、宽 3，覆盖第 2 到 4 列。
复杂度怎么算，哪些地方容易错
时间 O(R×C)：每行 O(C) 更新 heights 加 O(C) 单调栈（每根柱进出栈各一次），共 R 行。空间 O(C)：heights 数组与栈都只随列数增长，不需要二维辅助结构。
三个高频错误对应转化链上的三个环节：遇 0 不清零，柱状图本身就是错的；只算某一行、忘了对所有行取全局最大，而最大矩形的底行事先无从知晓；行内忘加末尾哨兵，栈里递增的尾巴没被结算，会漏掉答案。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
核心一句：0/1 矩阵的最大矩形 = 「逐行累加成柱状图 + 每行求柱状图最大矩形」的最大值。下面一行一行演示。
处理第 0 行：把它当柱状图的底。每一列从这行往上数连续的 1，就是这根柱子的高 —— heights = [1, 0, 1, 0, 0]（遇 0 的列被斩断清零）。下面对这张柱状图求最大矩形。
第 0 行：轮到柱 0（高 1）。栈空，没有更矮的栈顶要结算，直接入栈。
第 0 行：没有更矮的栈顶要结算，把柱 0（高 1）压入栈顶，栈仍保持递增。
第 0 行：轮到柱 1（高 0）。看栈顶柱 0（高 1）：当前更矮，栈顶再往右扩就被挡住，弹出它、以它为高算矩形。
第 0 行：弹出柱 0（高 1）。它向左只能扩到最左端，向右扩到柱 1（更矮挡住），高亮的 1 根就是它能罩住的最宽范围。矩形 = 高 1 × 宽 1 = 1。比之前的 0 大，全局最大更新为 1。
第 0 行：没有更矮的栈顶要结算，把柱 1（高 0）压入栈顶，栈仍保持递增。
第 0 行：轮到柱 2（高 1）。看栈顶柱 1（高 0）：当前不比栈顶矮，栈仍递增，直接入栈。
第 0 行：没有更矮的栈顶要结算，把柱 2（高 1）压入栈顶，栈仍保持递增。
第 0 行：轮到柱 3（高 0）。看栈顶柱 2（高 1）：当前更矮，栈顶再往右扩就被挡住，弹出它、以它为高算矩形。
第 0 行：弹出柱 2（高 1）。它向左只能扩到柱 1（更矮挡住），向右扩到柱 3（更矮挡住），高亮的 1 根就是它能罩住的最宽范围。矩形 = 高 1 × 宽 1 = 1。不及全局最大 1，最大不变。
第 0 行：没有更矮的栈顶要结算，把柱 3（高 0）压入栈顶，栈仍保持递增。
第 0 行：轮到柱 4（高 0）。看栈顶柱 3（高 0）：当前不比栈顶矮，栈仍递增，直接入栈。
第 0 行：没有更矮的栈顶要结算，把柱 4（高 0）压入栈顶，栈仍保持递增。
第 0 行：轮到末尾哨兵柱（高 0，灰色）。它比任何真实柱都矮，逼着把栈里没结算的柱子全弹出算一遍。
第 0 行扫描结束，哨兵入栈，本行所有柱都结算完。此刻全局最大面积 = 1。
处理第 1 行：把它当柱状图的底。每一列从这行往上数连续的 1，就是这根柱子的高 —— heights = [2, 0, 2, 1, 1]（遇 0 的列被斩断清零）。下面对这张柱状图求最大矩形。
第 1 行：轮到柱 0（高 2）。栈空，没有更矮的栈顶要结算，直接入栈。
第 1 行：没有更矮的栈顶要结算，把柱 0（高 2）压入栈顶，栈仍保持递增。
第 1 行：轮到柱 1（高 0）。看栈顶柱 0（高 2）：当前更矮，栈顶再往右扩就被挡住，弹出它、以它为高算矩形。
第 1 行：弹出柱 0（高 2）。它向左只能扩到最左端，向右扩到柱 1（更矮挡住），高亮的 1 根就是它能罩住的最宽范围。矩形 = 高 2 × 宽 1 = 2。比之前的 1 大，全局最大更新为 2。
第 1 行：没有更矮的栈顶要结算，把柱 1（高 0）压入栈顶，栈仍保持递增。
第 1 行：轮到柱 2（高 2）。看栈顶柱 1（高 0）：当前不比栈顶矮，栈仍递增，直接入栈。
第 1 行：没有更矮的栈顶要结算，把柱 2（高 2）压入栈顶，栈仍保持递增。
第 1 行：轮到柱 3（高 1）。看栈顶柱 2（高 2）：当前更矮，栈顶再往右扩就被挡住，弹出它、以它为高算矩形。
第 1 行：弹出柱 2（高 2）。它向左只能扩到柱 1（更矮挡住），向右扩到柱 3（更矮挡住），高亮的 1 根就是它能罩住的最宽范围。矩形 = 高 2 × 宽 1 = 2。不及全局最大 2，最大不变。
第 1 行：没有更矮的栈顶要结算，把柱 3（高 1）压入栈顶，栈仍保持递增。
第 1 行：轮到柱 4（高 1）。看栈顶柱 3（高 1）：当前不比栈顶矮，栈仍递增，直接入栈。
第 1 行：没有更矮的栈顶要结算，把柱 4（高 1）压入栈顶，栈仍保持递增。
第 1 行：轮到末尾哨兵柱（高 0，灰色）。它比任何真实柱都矮，逼着把栈里没结算的柱子全弹出算一遍。
第 1 行：弹出柱 4（高 1）。它向左只能扩到柱 3（更矮挡住），向右扩到柱 5（更矮挡住），高亮的 1 根就是它能罩住的最宽范围。矩形 = 高 1 × 宽 1 = 1。不及全局最大 2，最大不变。
第 1 行：弹出柱 3（高 1）。它向左只能扩到柱 1（更矮挡住），向右扩到柱 5（更矮挡住），高亮的 3 根就是它能罩住的最宽范围。矩形 = 高 1 × 宽 3 = 3。比之前的 2 大，全局最大更新为 3。
第 1 行扫描结束，哨兵入栈，本行所有柱都结算完。此刻全局最大面积 = 3。
处理第 2 行：把它当柱状图的底。每一列从这行往上数连续的 1，就是这根柱子的高 —— heights = [3, 1, 3, 2, 2]（遇 0 的列被斩断清零）。下面对这张柱状图求最大矩形。
第 2 行：轮到柱 0（高 3）。栈空，没有更矮的栈顶要结算，直接入栈。
第 2 行：没有更矮的栈顶要结算，把柱 0（高 3）压入栈顶，栈仍保持递增。
第 2 行：轮到柱 1（高 1）。看栈顶柱 0（高 3）：当前更矮，栈顶再往右扩就被挡住，弹出它、以它为高算矩形。
第 2 行：弹出柱 0（高 3）。它向左只能扩到最左端，向右扩到柱 1（更矮挡住），高亮的 1 根就是它能罩住的最宽范围。矩形 = 高 3 × 宽 1 = 3。不及全局最大 3，最大不变。
第 2 行：没有更矮的栈顶要结算，把柱 1（高 1）压入栈顶，栈仍保持递增。
第 2 行：轮到柱 2（高 3）。看栈顶柱 1（高 1）：当前不比栈顶矮，栈仍递增，直接入栈。
第 2 行：没有更矮的栈顶要结算，把柱 2（高 3）压入栈顶，栈仍保持递增。
第 2 行：轮到柱 3（高 2）。看栈顶柱 2（高 3）：当前更矮，栈顶再往右扩就被挡住，弹出它、以它为高算矩形。
第 2 行：弹出柱 2（高 3）。它向左只能扩到柱 1（更矮挡住），向右扩到柱 3（更矮挡住），高亮的 1 根就是它能罩住的最宽范围。矩形 = 高 3 × 宽 1 = 3。不及全局最大 3，最大不变。
第 2 行：没有更矮的栈顶要结算，把柱 3（高 2）压入栈顶，栈仍保持递增。
第 2 行：轮到柱 4（高 2）。看栈顶柱 3（高 2）：当前不比栈顶矮，栈仍递增，直接入栈。
第 2 行：没有更矮的栈顶要结算，把柱 4（高 2）压入栈顶，栈仍保持递增。
第 2 行：轮到末尾哨兵柱（高 0，灰色）。它比任何真实柱都矮，逼着把栈里没结算的柱子全弹出算一遍。
第 2 行：弹出柱 4（高 2）。它向左只能扩到柱 3（更矮挡住），向右扩到柱 5（更矮挡住），高亮的 1 根就是它能罩住的最宽范围。矩形 = 高 2 × 宽 1 = 2。不及全局最大 3，最大不变。
第 2 行：弹出柱 3（高 2）。它向左只能扩到柱 1（更矮挡住），向右扩到柱 5（更矮挡住），高亮的 3 根就是它能罩住的最宽范围。矩形 = 高 2 × 宽 3 = 6。比之前的 3 大，全局最大更新为 6。
第 2 行：弹出柱 1（高 1）。它向左只能扩到最左端，向右扩到柱 5（更矮挡住），高亮的 5 根就是它能罩住的最宽范围。矩形 = 高 1 × 宽 5 = 5。不及全局最大 6，最大不变。
第 2 行扫描结束，哨兵入栈，本行所有柱都结算完。此刻全局最大面积 = 6。
处理第 3 行：把它当柱状图的底。每一列从这行往上数连续的 1，就是这根柱子的高 —— heights = [4, 0, 0, 3, 0]（遇 0 的列被斩断清零）。下面对这张柱状图求最大矩形。
第 3 行：轮到柱 0（高 4）。栈空，没有更矮的栈顶要结算，直接入栈。
第 3 行：没有更矮的栈顶要结算，把柱 0（高 4）压入栈顶，栈仍保持递增。
第 3 行：轮到柱 1（高 0）。看栈顶柱 0（高 4）：当前更矮，栈顶再往右扩就被挡住，弹出它、以它为高算矩形。
第 3 行：弹出柱 0（高 4）。它向左只能扩到最左端，向右扩到柱 1（更矮挡住），高亮的 1 根就是它能罩住的最宽范围。矩形 = 高 4 × 宽 1 = 4。不及全局最大 6，最大不变。
第 3 行：没有更矮的栈顶要结算，把柱 1（高 0）压入栈顶，栈仍保持递增。
第 3 行：轮到柱 2（高 0）。看栈顶柱 1（高 0）：当前不比栈顶矮，栈仍递增，直接入栈。
第 3 行：没有更矮的栈顶要结算，把柱 2（高 0）压入栈顶，栈仍保持递增。
第 3 行：轮到柱 3（高 3）。看栈顶柱 2（高 0）：当前不比栈顶矮，栈仍递增，直接入栈。
第 3 行：没有更矮的栈顶要结算，把柱 3（高 3）压入栈顶，栈仍保持递增。
第 3 行：轮到柱 4（高 0）。看栈顶柱 3（高 3）：当前更矮，栈顶再往右扩就被挡住，弹出它、以它为高算矩形。
第 3 行：弹出柱 3（高 3）。它向左只能扩到柱 2（更矮挡住），向右扩到柱 4（更矮挡住），高亮的 1 根就是它能罩住的最宽范围。矩形 = 高 3 × 宽 1 = 3。不及全局最大 6，最大不变。
第 3 行：没有更矮的栈顶要结算，把柱 4（高 0）压入栈顶，栈仍保持递增。
第 3 行：轮到末尾哨兵柱（高 0，灰色）。它比任何真实柱都矮，逼着把栈里没结算的柱子全弹出算一遍。
第 3 行扫描结束，哨兵入栈，本行所有柱都结算完。此刻全局最大面积 = 6。
所有行都求过一次柱状图最大矩形，全局最大出现在第 2 行：高 2、宽 3、覆盖列 2~4，面积 = 2 × 3 = 6。对应回原矩阵，就是那块全 1 的最大矩形。
空 / 全 0 / 全 1 三种边界先想清楚。
两个高频追问：二维转一维的合理性、与 LC84 的母子关系。
参考代码
def maximalRectangle(matrix): if not matrix: return 0 C = len(matrix[0]) heights = [0] * C # 逐行累加的柱高 best = 0 for row in matrix: for c in range(C): # 遇 1 高度+1，遇 0 清零 heights[c] = heights[c] + 1 if row[c] == "1" else 0 best = max(best, largest(heights)) # LC84 return bestdef largest(hs): # 柱状图最大矩形·单调递增栈 hs = hs + [0]; st = []; b = 0 for i, h in enumerate(hs): while st and h < hs[st[-1]]: top = st.pop() left = st[-1] if st else -1 b = max(b, hs[top] * (i - left - 1)) st.append(i) return b复杂度
- 时间：O(R×C)，每行 O(C) 累加 + O(C) 单调栈，共 R 行
- 空间：O(C)，heights 数组 + 单调栈各 O(C)
易错点
面试追问把动画讲成自己的话
追问为什么能把二维问题拆成逐行的柱状图？
追问和 LC84「柱状图最大矩形」是什么关系？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
简化路径
LeetCode 71 · 中等 · 沿着 栈 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题