我整理 LeetCode 刷题记录时，经常会把那些“第一眼觉得是中等题、写起来全是坑”的题目单独挑出来重刷。最大矩形就是特别典型的一道，它在很多公司的算法面试里出现频率不低，解法路径又很清晰：表面是二维图形题，内核却是一维柱状图最大矩形，还顺带把高频考点单调栈串了起来。更常见的情况是，很多刷题人会把它和“最大正方形”搞混，以为能套同一个 DP 公式，结果推了半天发现卡住。这篇记录是我自己三刷这道题之后的完整复盘，适合正在刷动态规划和单调栈的读者，也适合面试前想快速捡起高频题的人。
先说我的经历。第一遍刷到它，我老老实实写了四层循环去枚举矩形，提交直接超时；第二遍用了列前缀和枚举上下边界，勉强通过，但代码又长又啰嗦，面试场景下根本讲不清楚；直到第三遍认真复习了 84 题“柱状图中最大的矩形”的单调栈解法，才突然意识到：把二维矩阵按行切，每一行上方连续为 1 的部分，其实是一张柱状图。这个“按行切”的想法，才是整道题的题眼。
1. 一道刷了三遍才彻底吃透的题目
1.1 为什么值得单独记一份
这道题的问题描述很简短：给定一个仅包含 0 和 1 的二维矩阵，找出只包含 1 的最大矩形面积。难点不在读题，而在于切入点。很多人第一反应是“能不能像最大连续子序列那样用 DP 扫一遍”，我也试过，DP 状态很难定义，因为最大矩形的面积由底边宽度和高度两个因子共同决定，局部最优没法简单合并。真实面试里，如果往这个方向硬钻，很快会卡住。
我在草稿纸上试过用 dp[i][j] 表示以 (i,j) 为右下角的最大矩形面积，发现它同时依赖上方高度和向左延伸的宽度，这两个量要塞进同一个状态，状态转移非常别扭。反而是“固定底边”这个思路，一开始不太起眼，但能直接把问题打穿。等我把这条思路和 84 题的单调栈解法挂钩之后，代码量瞬间少了一大截，而且每一步都能讲清楚为什么。
1.2 第一版暴力做法错在哪
暴力法的思路很自然：枚举矩形的左上角 (i1,j1) 和右下角 (i2,j2)，再验证这个子矩形里是不是全 1。如果矩阵规模是 m 行 n 列，上下边界有 O(m^2) 种选择，左右边界有 O(n^2) 种选择，组合起来就是 O(m^2 n^2) 个子矩形。每个子矩形如果暴力扫描验证全 1，又是 O(m n)，总复杂度直接到 O(m^3 n^3)。就算用二维前缀和把“验证全 1”降到 O(1)，四个边界的枚举依然存在，本质瓶颈没有解决，100×100 左右的矩阵勉强能跑，1000×1000 就只能放弃。
要降复杂度，必须减少枚举维度。我发现关键点在于：一旦确定了矩形的下边界在哪一行，矩形的高度其实由每一列“向上连续 1 的长度”决定，不再需要单独枚举上边界。每一列向上连续 1 的长度可以滚动计算，于是二维矩阵被压成了一条一维高度数组，二维面积问题就变成了若干次一维柱状图最大矩形问题。这个转化第一次见会觉得有点绕，但亲手推导一个例子之后，后面基本不会再忘。
2. 从暴力枚举到一维柱状图：转化过程为什么成立
2.1 固定下边界怎么消掉一维
我这样理解这个转化：任意一个全 1 矩形，它总有一个底边所在的行。假设底边在第 r 行，那么从这个矩形底边向上看，每一列能延伸多高，取决于这一列从第 r 行往上连续出现了多少个 1。一旦某列在第 r 行到某个位置之间出现了 0，矩形就不能跨过这个 0。所以“以第 r 行为底边的最大全 1 矩形”，完全等价于在一张柱状图里找最大矩形，柱子高度就是各列向上连续 1 的个数。
柱状图的高度数组可以滚动更新。height[j] 表示当前列从当前处理的行往上，连续出现 1 的个数。当处理第 r 行时，如果 matrix[r][j] 是 1，说明延续了上一行的连续性，height[j] 加一；如果 matrix[r][j] 是 0，说明连续性中断，height[j] 清零。这个清零点非常重要，下面会专门展开。
我建议亲手推一次例子，比如矩阵 [[1,0,1],[1,1,1],[1,1,1]]。第 0 行处理完后 height=[1,0,1]；第 1 行处理完后变成 [2,1,2]；第 2 行处理完后变成 [3,2,3]。以第 2 行为底边时，宽度 1 高度 3 的矩形面积是 3，宽度 2 高度 2 的矩形面积是 4，宽度 3 高度 1 的矩形面积是 3，最大是 4。这个 4 正好是原矩阵里包含第 2 行、能往上延伸的最大全 1 矩形面积。
2.2 为什么这里不适合直接 DP
最大矩形不能像最大正方形那样用一个简单 DP 递推，核心原因是矩形不要求宽高相等。最大正方形能定义 dp[i][j] 表示以 (i,j) 为右下角的最大正方形边长，因为正方形的宽高必须相等，只要左方、上方、左上方三个位置的正方形都成立，当前位置才能扩展。而最大矩形只要求面积最大，宽和高可以任意比例，局部的三个方向约束根本无法浓缩成一个状态。
我发现一个很实用的判断技巧：拿到一道题，先问自己答案能不能被一个“以某个位置为右下角”的状态完全描述出来。如果不能，大概率不是普通二维 DP，而是需要转化成其它结构。最大矩形就是典型的“要用一维柱状图结构”的题。
2.3 前置知识：柱状图最大矩形的单调栈原理
既然核心变成了“求一维柱状图最大矩形”，那就要先吃透 84 题。单调栈的做法是维护一个栈，栈里存下标，从栈底到栈顶对应的高度严格递增。遍历柱状图时，如果当前柱子的高度比栈顶柱子的高度矮，说明以栈顶柱子为高的矩形已经没法继续向右扩展了，于是弹出栈顶并结算面积。
结算时，矩形的高度就是被弹出柱子的高度。宽度怎么算？要取“当前遍历到的柱子下标 i”和“弹出后新的栈顶下标 left”之间的距离，也就是 i - left - 1。这看起来有点绕，因为中间那些高度比被弹出柱子更高的柱子，它们的宽度实际上都能一起算进面积里。在数组末尾补一个高度为 0 的哨兵，可以确保最后栈里所有柱子都被弹出来结算，不用单独处理循环结束的情况。这个哨兵技巧在最大矩形里也能直接用。
3. 单调栈完整落地：每一行做一次一维最大矩形
3.1 两层循环组合的思路
整体结构是两层循环：外层遍历矩阵的每一行，内层先更新高度数组，再调用一维柱状图最大矩形求解，更新全局最大值。外层是 O(m)，内层是 O(n)，总复杂度 O(m n)。这里有一个特别容易写错的地方：高度数组不能在每一行开始时重置，只能在遇到 0 时清零。它本质上是一个带断点的累加器，保留上一行的信息，才能体现“向上连续 1 的长度”。
我建议把一维求解独立成一个函数，比如叫 largest_rectangle_area。外层代码就非常干净：每处理完一行，就把它对应的 height 数组交给这个函数算一次。面试时这样拆分，面试官也能顺着你的结构理解思路。
3.2 代码实现逐行解读
我用 Python 写一版最容易读的：
def maximal_rectangle(matrix): if not matrix or not matrix[0]: return 0 rows, cols = len(matrix), len(matrix[0]) heights = [0] * cols max_area = 0 for r in range(rows): for c in range(cols): if matrix[r][c] == '1': heights[c] += 1 else: heights[c] = 0 max_area = max(max_area, largest_rectangle_area(heights)) return max_area def largest_rectangle_area(heights): stack = [] heights = heights + [0] max_area = 0 for i, h in enumerate(heights): while stack and heights[stack[-1]] > h: cur = stack.pop() left = stack[-1] if stack else -1 width = i - left - 1 max_area = max(max_area, heights[cur] * width) stack.append(i) return max_area逐行看几个关键点。第一，判断字符时要写成 matrix[r][c] == '1'，不是 == 1。LeetCode 这道题的常见输入是字符二维数组，如果你在本地用整数 0/1 测试，提交时很容易忽略这个差异。第二，单调栈里用 > 还是 >= 都可以，但我实测用 > 配合哨兵 0 最不容易写错。遇到相等高度时不弹出，等遇到更矮的高度时统一结算，逻辑更一致。第三，算宽度时用的是弹出后新的栈顶下标 left，不是当前弹出的柱子 cur 自己，因为 cur 只是高度，中间那些比 cur 高的柱子也要算进宽度里。
3.3 一次手动模拟加深理解
拿 heights = [2,1,5,6,2,3] 举例。遍历到下标 1 高度 1 时，栈里已经有下标 0 高度 2，2 > 1，所以弹出下标 0，此时 left 是 -1，宽度 = 1 - (-1) - 1 = 1，面积 = 2×1=2。这个矩形的含义是：以高度 2 的柱子为高，它左边边界是 -1（没有更矮的柱子），右边边界是下标 1（遇到高度 1 被挡住），宽度只有自己这一根。继续遍历，到下标 4 高度 2 时，栈顶是下标 3 高度 6，6 > 2，弹出下标 3，此时栈顶是下标 2 高度 5，宽度 = 4 - 2 - 1 = 1，面积 = 6×1=6；继续弹出下标 2，此时栈顶是下标 1 高度 1，宽度 = 4 - 1 - 1 = 2，面积 = 5×2=10。这就是柱状图最大矩形 10 的来源。把这段逻辑放进每一行的高度数组里，整体就通了。
4. 实际刷题时最容易翻车的几个细节
4.1 空矩阵和边界判断
删除 if not matrix or not matrix[0]: return 0 会出问题。matrix = [] 时，直接访问 matrix[0] 会越界；matrix = [[]] 时，虽然 matrix 本身非空，但 matrix[0] 是空列表，列数为 0。所以一定要把两个条件一起写。我见过不少人只写 if not matrix: return 0，然后就挂在空行的测试用例上。
只有一列的情况也值得单独想一下。比如 [[“1”], [“1”], [“0”]]，height 数组始终只有一个元素在变化，本质是求连续 1 的最大长度。这个场景下单调栈依然有效，不需要特判。只要矩阵的行数或列数至少有一个大于 0，就按通用流程走。
4.2 0 的清零逻辑不能漏
最隐蔽的坑就在高度数组的清零。有人写更新逻辑时只写了 if matrix[r][c] == '1': heights[c] += 1，忘记 else 清零。这样一旦某列在当前行遇到 0，上一行的连续高度还留在数组里，下一行再遇到 1，高度会错误地延续，最终算出一个偏大的假答案。我第一版就是这么错的，而且因为小样例碰巧能过，排查了很久才发现。
清零的本质是模拟“连续性中断”。0 就相当于一堵墙，矩形不能穿过它，所以这一列的有效高度必须归零。理解这个语义之后，就不容易漏掉了。
4.3 和最大正方形 DP 的混淆
最大正方形有一条很漂亮的 DP 递推：dp[i][j] 等于左、上、左上三个位置的 dp 值取最小再加 1。最大矩形没有同样漂亮的递推，因为矩形不要求宽高相等。很多人会把这两道题放在一起刷，然后试图用同一个状态转移去套，结果在最大矩形上反复碰壁。
我的经验是：如果一道二维矩阵题卡在一个 DP 定义上超过十分钟，就先停一下，想想能不能通过固定某一边把问题压成一维。最大矩形就是“固定底边”的典型例子；最大正方形则因为形状约束，天然适合“固定右下角”。两道题放一起对比复习，反而是理解两者本质的最佳方式。
5. 面试怎么讲才加分：从暴力到单调栈的推导路径
5.1 递进式回答更让人信服
面试官如果出这道题，最怕遇到直接甩单调栈代码的候选人。背答案不等于理解。更好的打开方式是：先说暴力四重循环，说明复杂度是 O(m^2 n^2)，矩阵稍大就不行；然后说可以用二维前缀和把“验证全 1”降到 O(1)，但边界枚举还是 O(m^2 n^2)；再补一句“如果固定底边，问题就变成一维柱状图最大矩形，可以用单调栈在 O(n) 内求解”。这样一步一步递进，面试官能看到你的思考路径。
5.2 复杂度和空间最优的追问
如果被追问“能不能继续优化”，要能接得住。对于稠密矩阵，O(m n) 已经是最优，因为每个元素至少需要读一次；对于稀疏矩阵，可以讨论按连续 1 的区间做分治优化，但这属于进阶话题，通常不会被要求现场写。空间上，只需要 O(n) 的高度数组，不需要存额外的 O(m n) 中间状态。
如果再被追问“如果要把最大矩形的具体位置也输出怎么办”，就要在结算面积时记录四个边界：底边行号就是当前处理到的行 r；顶边行号是 r - heights[cur] + 1；左边界是 left + 1；右边界是 i - 1。能答出这一步，说明你对栈里下标和宽度的来源是真懂，而不是背代码。
5.3 把一题多解写进刷题记录的价值
我的刷题记录里，这道题保留了三个版本的解法：暴力枚举、前缀和加枚举上下边界、单调栈。每版都写清楚“为什么慢”和“为什么快”。等到面试时，我直接复述这条递进路径，效果比只说一个最优解好很多。这也是我一直坚持完整记录 LeetCode 刷题记录的原因：不是写给别人看，是写给三个月后的自己。再过一段时间翻出来，我能一眼想起题眼、坑点和面试话术。
6. 复现清单和后续扩展
6.1 我用来验证的测试用例
建议刷完这道题后，至少跑一遍下面这些用例：
| 输入 | 期望输出 | 说明 |
|---|---|---|
[] | 0 | 空矩阵 |
[[]] | 0 | 只有空行 |
[["0"]] | 0 | 单个 0 |
[["1"]] | 1 | 单个 1 |
[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] | 6 | 题目经典样例 |
| 3 行 4 列全 1 | 12 | 整个矩阵都是 1 |
[["1","1","1","1"],["1","1","1","1"],["0","1","1","1"]] | 9 | 两行全 1 加一行前三列连续 |
最后一个用例很适合用来验证清零逻辑。前两行处理完后 heights 是 [2,2,2,2]，第三行遇到第一列的 0，heights 变成 [0,3,3,3]，最大矩形是宽 3 高 3 面积 9。如果没有清零，第三行那列还保留旧高度 2，后面几列又累加，结果会错算成一个更大的假矩形。
6.2 和同类题串起来复习
做完这道题，强烈建议把“柱状图中最大的矩形”和“接雨水”放在一起看。这三题共用单调栈骨架，区别只在结算时机和高度合法性判断：接雨水按波峰波谷结算水量，柱状图按“当前柱子为高”结算面积，最大矩形是每一行套一次柱状图。我是在连续刷完三题之后，才真正把单调栈变成肌肉记忆。从那以后，遇到类似的几何面积问题，我会先想：能不能把二维问题压成一维？能不能用单调栈维护一个单调关系？
6.3 给未来的自己留一份可复习的笔记
如果你也在刷这道题，我建议用自己的话写一份记录，包含四部分：题目名和题眼、错误尝试、正确解法和复杂度、以及一句话的面试话术。题眼是“按行切成一维柱状图”，最容易错的是“0 要清零”，面试里要讲清楚“从暴力到单调栈的推导路径”。等这套笔记你重复三遍以上，这道题就真的属于你了。
最后分享一个小技巧：面试时间紧张时，可以先只写一维的 largest_rectangle_area，然后对外层说“对每一行维护高度数组后调用它”。我试过，这种先核心后组装的方式，比闷头写一长串代码更能让面试官跟着你的思路走。等代码跑通之后再补外层循环，既不会乱，也不容易在压力下丢边界条件。
