我整理 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 高度 22 1所以弹出下标 0此时 left 是 -1宽度 1 - (-1) - 1 1面积 2×12。这个矩形的含义是以高度 2 的柱子为高它左边边界是 -1没有更矮的柱子右边边界是下标 1遇到高度 1 被挡住宽度只有自己这一根。继续遍历到下标 4 高度 2 时栈顶是下标 3 高度 66 2弹出下标 3此时栈顶是下标 2 高度 5宽度 4 - 2 - 1 1面积 6×16继续弹出下标 2此时栈顶是下标 1 高度 1宽度 4 - 1 - 1 2面积 5×210。这就是柱状图最大矩形 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 列全 112整个矩阵都是 1[[1,1,1,1],[1,1,1,1],[0,1,1,1]]9两行全 1 加一行前三列连续最后一个用例很适合用来验证清零逻辑。前两行处理完后 heights 是 [2,2,2,2]第三行遇到第一列的 0heights 变成 [0,3,3,3]最大矩形是宽 3 高 3 面积 9。如果没有清零第三行那列还保留旧高度 2后面几列又累加结果会错算成一个更大的假矩形。6.2 和同类题串起来复习做完这道题强烈建议把“柱状图中最大的矩形”和“接雨水”放在一起看。这三题共用单调栈骨架区别只在结算时机和高度合法性判断接雨水按波峰波谷结算水量柱状图按“当前柱子为高”结算面积最大矩形是每一行套一次柱状图。我是在连续刷完三题之后才真正把单调栈变成肌肉记忆。从那以后遇到类似的几何面积问题我会先想能不能把二维问题压成一维能不能用单调栈维护一个单调关系6.3 给未来的自己留一份可复习的笔记如果你也在刷这道题我建议用自己的话写一份记录包含四部分题目名和题眼、错误尝试、正确解法和复杂度、以及一句话的面试话术。题眼是“按行切成一维柱状图”最容易错的是“0 要清零”面试里要讲清楚“从暴力到单调栈的推导路径”。等这套笔记你重复三遍以上这道题就真的属于你了。最后分享一个小技巧面试时间紧张时可以先只写一维的 largest_rectangle_area然后对外层说“对每一行维护高度数组后调用它”。我试过这种先核心后组装的方式比闷头写一长串代码更能让面试官跟着你的思路走。等代码跑通之后再补外层循环既不会乱也不容易在压力下丢边界条件。