刷 LeetCode 85 这道题之前我其实已经把 84柱状图中最大的矩形来回刷了好几遍自认为单调栈玩得挺熟。结果看到 Maximal Rectangle 的输入是个二维矩阵一下子还是懵了柱子在哪高度怎么定义二维矩阵里的“矩形面积”和“直方图面积”到底怎么能扯上关系那天晚上我在草稿纸上画了不知道多少遍示例矩阵才终于把“逐行压成直方图再对每一行跑一遍 84 的单调栈”这条链路彻底想通。这篇题解我不想只丢一个 AC 代码而是把从暴力到最优的完整思考链路、关键推导、手工模拟和实际提交时踩过的坑都梳理出来。无论你是刚刷到 84/85 的新手还是想把这道题变成固定套路的老手照着这个思路走一遍应该都能直接上手自己写出来。1. 这道题到底在求什么题面、例子和边界1.1 示例里的答案是 6它是怎么画出来的题目给一个 m×n 的矩阵里面只有字符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。它对应的是第 1、2 行从 0 开始数和第 2、3、4 列围出来的 2×3 区域也就是这两行三列交叉出的 6 个格子全部是 1。之前有不少人第一次看这个例子会困惑左上角不是有两个 1 吗为什么不用它们因为第 0 行中间有一个 0任何想跨到第 0 行的矩形列集合都必须躲开这个 0宽度就会受限制拼出来的面积反而不如 6 大。这个细节恰好引出了这道题最核心的矛盾矩形想横向宽每一行的列区间里都不能有 0 挡路矩形想纵向高每一列都得连续向上攒 1。两个方向的约束交织在一起才是 Maximal Rectangle 真正要处理的东西。1.2 输入规模和数据特征LeetCode 的约束是矩阵行数和列数最大都是 200。这个规模其实有点微妙它允许你写出 O(m²n) 的算法大概 8×10⁶ 量级在多数语言里擦边通过但最优解是 O(mn) 的单调栈做法。更关键的是矩阵里存的是字符1和0不是整数 1 和 0。这一点看着不起眼实际写代码时非常容易翻车我后面专门有一节讲这个坑。另外题目虽然保证了矩阵至少有一行一列但自己写工具函数时最好还是把空矩阵的判断带上这是一个能帮你省掉很多无谓 WA 的好习惯。2. 直面复杂度瓶颈枚举矩形为什么不行行对压缩又为什么能跑2.1 最朴素暴力四个角都枚举一遍拿到这道题第一反应肯定是暴力枚举。最直白的写法是枚举左上角(r1, c1)和右下角(r2, c2)然后检查这个子矩阵里是不是全为 1。光矩形的数量就是 m(m1)/2 × n(n1)/2当 mn200 时大约是 4 亿个子矩形。就算你用二维前缀和把“检查是否全 1”优化到 O(1)也还要跑 4 亿次操作Python 基本没戏C 也是勉强。如果不做前缀和每次再去扫描矩形内部复杂度直接爆炸到 O(m³n³)那就更不用聊了。暴力枚举不是没有价值它的价值在于帮我们确认了一个事实矩形本质上由“行的上下边界”和“列的左右边界”四根线决定。想要降低复杂度必须想办法少枚举一个维度。2.2 更聪明的 O(m²n) 行对压缩换个角度想如果我先固定矩形的上边界 top 和下边界 bottom问题就变成了一维的。对于这一对上下界每一列在[top, bottom]这一段里要么全是 1要么至少有一个 0。我们把全是 1 的列叫“有效列”那么任何一段连续的“有效列”配上当前的 top、bottom就是一个合法的全 1 矩形。于是问题退化成在一串 01 状态里找最长的连续 1 段再乘以高度bottom - top 1。判断一列是否全 1不需要每次重新扫一遍行可以预处理每一列的“1 的个数前缀和”。用ps[i][j]表示第 j 列从第 0 行到第 i 行一共有多少个 1那么列 j 在[top, bottom]里的 1 的数量就等于ps[bottom][j] - ps[top-1][j]这个值刚好等于bottom - top 1就说明它是有效列。枚举所有 top、bottom 是 O(m²)对每一对上下界扫一遍 n 列是 O(n)总复杂度 O(m²n)。因为 n 最大只有 200这个解法实际上也能跑进时限。def maximalRectangle_rowpair(matrix): if not matrix or not matrix[0]: return 0 m, n len(matrix), len(matrix[0]) # ps[i][j] 表示第 j 列从第 0 行累计到第 i 行的 1 的个数 ps [[0] * n for _ in range(m)] for i in range(m): for j in range(n): ps[i][j] int(matrix[i][j] 1) (ps[i - 1][j] if i else 0) ans 0 for top in range(m): for bottom in range(top, m): h bottom - top 1 run 0 # 当前连续有效列的长度 for j in range(n): cnt ps[bottom][j] - (ps[top - 1][j] if top else 0) valid (cnt h) run run 1 if valid else 0 ans max(ans, run * h) return ans2.3 为什么行对压缩依然不是终点如果只是追求 ACO(m²n) 已经可以交差了。但 LeetCode 把 85 放在 84 后面是有意图的它希望你从一维直方图迁移到二维矩阵。面试官大概率也会追问“还有没有更优的做法”。单调栈解法能把时间压到 O(mn)而且它的思想更通用以后遇到类似的“最大子矩形”问题都能用。行对压缩真正的价值是帮我们建立了一个关键视角一列能不能“用”取决于这段行区间内有没有 0。那如果我们不固定上下界而是让每一列自己向上“累积连续 1 的个数”是不是就能把一个二维问题彻底压成一维下一节就是这个视角的自然延伸。3. 把矩阵压成一排排柱状图heights 的构造与意义3.1 heights 的递推规则核心做法是维护一个一维数组heights[j]它表示扫描到当前第 i 行时第 j 列从下往上连续有多少个 1。你可以把每一行想象成一块水平地板heights[j]就是在这块地板上第 j 列的位置叠起来的柱子高度。更新规则非常朴素如果matrix[i][j] 1heights[j]加 1如果matrix[i][j] 0heights[j]直接归零。归零那一步极其关键。0 意味着纵向的“连续性”在这里断掉了之前攒了多少层都作废因为任何跨过这个 0 的矩形底部都会缺一块。把归零理解成“地基塌了柱子要重新盖”就很好记。3.2 在示例矩阵上手工推一遍用题目示例一行一行推能得到下面这张表当前行本行原始内容更新后的 heights该行直方图的最大矩形面积01 0 1 0 0[1, 0, 1, 0, 0]111 0 1 1 1[2, 0, 2, 1, 1]321 1 1 1 1[3, 1, 3, 2, 2]631 0 0 1 0[4, 0, 0, 3, 0]4第四列“该行直方图的最大矩形面积”需要用到柱状图求最大矩形的算法也就是 LeetCode 84。以第 2 行为例[3, 1, 3, 2, 2]这个直方图里高度为 2 的柱子从第 2 列延伸到第 4 列能撑起一个 2×36 的矩形正好就是答案。3.3 为什么原题答案等于所有行直方图的最大值这一步的等价性需要说清楚。假设矩阵里有一个以第 i 行为底边的全 1 矩形宽 w、高 h那么它覆盖的 w 列在i-h1到i这段行里肯定全是 1。也就是说这 w 列在第 i 行时的heights值至少是 h。把这几根柱子单独拎出来看它们就是直方图里一个宽 w、高 h 的矩形。反过来如果某一行直方图里存在一个宽 w、高 h 的矩形说明有连续 w 列的柱子高度都不小于 h把这几列往下数 h 行对应区域的矩阵格子也一定全是 1。两边是一一对应的因此“以第 i 行为底边的最大矩形面积”就等于“第 i 行 heights 直方图的最大矩形面积”。扫描完整张矩阵取所有行的最大值就是原题的答案。4. 直方图求最大矩形的单调栈原理与手工模拟4.1 从“每根柱子能撑多宽”说起现在的子问题就是标准的一维直方图给定非负整数数组 heights求里面能画出的最大矩形面积。最朴素的思路是枚举每一根柱子以这根柱子的高度作为矩形高度然后向左向右扩展直到遇到一根更矮的柱子为止。矩形的高度不可能超过区间里最矮的那根柱子所以“以第 j 根柱子的高度为高”的最大矩形宽度就是左右两边最近矮柱子之间的距离。问题是如果对每一根柱子都往左右扫一遍最坏情况是 O(n²)。单调栈要做的就是一件事在一次从左到右的扫描里同时维护出每一根柱子左边最近的矮柱子和右边最近的矮柱子。4.2 单调栈为什么能维护左右边界栈里存的是柱子的下标并且从栈底到栈顶下标对应的柱子高度严格递增。为什么要有这个单调性因为当我们从左往右看到一根新柱子时如果它比栈顶柱子矮或者一样高那么栈顶那根柱子的“右边界”就确定了——它不可能再往右扩展了新来的这根就是挡住它的墙。这时候把栈顶弹出来结算右边界 right 就是当前遍历到的下标 i左边界 left 是弹出后新的栈顶下标也就是左边最近的一根比它矮的柱子如果弹出后栈空了说明左边没有更矮的柱子left 记为 -1矩形宽度 right - left - 1面积 弹出柱子高度 × 宽度。这里我推荐统一用作为弹出条件。用会让相等高度的柱子也提前结算栈内保持严格递增真正负责最宽矩形的是留在栈里的那根同高度柱子整体最大面积不会丢。这个等号细节有很多人纠结后面踩坑节我会展开讲。4.3 用 [2,1,5,6,2,3] 完整走一遍栈纸上谈兵容易晕拿 LeetCode 84 的经典例子[2,1,5,6,2,3]完整走一遍。为了清空栈我在数组末尾加一个高度为 0 的哨兵所以实际遍历的是[2,1,5,6,2,3,0]iheights[i]动作弹出下标弹出高度leftrightwidtharea02压栈------11弹 0再压 102-111225压栈------36压栈------42弹 3、弹 2再压 436241642继续弹251421053压栈------60哨兵弹 5、弹 4、弹 153461360继续弹42164860继续弹11-1666记录到的最大面积是 10和标准答案一致。注意看下标 4 那一步新来的高度 2 把高度 6 和 5 都弹了出去因为它们都没法再向右扩展而高度 5 那根柱子左边最近的矮柱子是下标 1高度 1右边是下标 4高度 2所以宽度是4 - 1 - 1 2面积 10。这个“弹出时才结算”的时机是整个算法的精髓。4.4 哨兵 0 的作用循环结束后栈里可能还有柱子没结算因为它们右边没有更矮的柱子出现。最优雅的做法是在数组末尾补一个高度 0 的哨兵让它们在最后一轮被强制弹出。哨兵本身高度为 0不会产生正面积但能让代码逻辑统一少写一个 for 循环处理栈内残留。实现的时候注意Python 里heights [0]会生成新列表原数组不受影响如果写成原地append(0)一定要考虑会不会污染外部数据这个坑后面专门讲。def largestRectangleArea(heights): stack [] max_area 0 for i, h in enumerate(heights [0]): while stack and heights[stack[-1]] h: idx stack.pop() height heights[idx] left stack[-1] if stack else -1 width i - left - 1 max_area max(max_area, height * width) stack.append(i) return max_area5. 完整题解代码Python 与 C 的落地写法5.1 Python 实现把第三、四节的内容拼起来就是完整题解。外层循环负责逐行更新 heights内层调用 84 的直方图函数取最大值from typing import List 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]) heights [0] * n best 0 for i in range(m): # 更新每一列的连续 1 高度 for j in range(n): if matrix[i][j] 1: heights[j] 1 else: heights[j] 0 # 当前行作为底边的直方图求一次最大矩形 best max(best, self.largestRectangleArea(heights)) return best def largestRectangleArea(self, heights: List[int]) - int: stack [] max_area 0 # 末尾补 0 哨兵强制清空栈 for i, h in enumerate(heights [0]): while stack and heights[stack[-1]] h: idx stack.pop() height heights[idx] left stack[-1] if stack else -1 width i - left - 1 max_area max(max_area, height * width) stack.append(i) return max_area写的时候有几个地方要特别留意maximalRectangle里heights是复用的每一行先更新再求面积顺序不能反largestRectangleArea里heights [0]是生成新列表不会污染外层弹栈时left要用“弹出后”的栈顶所以必须先把idx弹出来再算left。5.2 C 实现C 版本在结构上完全一样唯一的陷阱在于传参。如果把largestRectangleArea写成引用传参又在函数里heights.push_back(0)那会直接改动外层数组下一行再调用时数组长度就多出来了。最稳妥的方法是按值传参让函数内部对副本任意操作或者用完后pop_back()恢复class Solution { public: int maximalRectangle(vectorvectorchar matrix) { if (matrix.empty() || matrix[0].empty()) return 0; int m matrix.size(), n matrix[0].size(); vectorint heights(n, 0); int best 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (matrix[i][j] 1) heights[j]; else heights[j] 0; } best max(best, largestRectangleArea(heights)); } return best; } int largestRectangleArea(vectorint heights) { // 按值传参内部 push_back 不污染外部 stackint st; int maxArea 0; heights.push_back(0); for (int i 0; i (int)heights.size(); i) { while (!st.empty() heights[st.top()] heights[i]) { int idx st.top(); st.pop(); int h heights[idx]; int left st.empty() ? -1 : st.top(); int width i - left - 1; maxArea max(maxArea, h * width); } st.push(i); } return maxArea; } };5.3 复杂度分析和两个子函数的边界时间复杂度是 O(mn)因为外层遍历 m 行每行更新 heights 要 O(n)直方图函数里每根柱子最多入栈一次、出栈一次也是 O(n)合计 O(mn)。空间复杂度是 O(n)主要花在 heights 数组和单调栈上。这个复杂度是这道题的最优级别面试时如果能口算出这两条基本就是加分项。边界情况也要在代码里覆盖住矩阵为空、矩阵只有一行、矩阵只有一列、矩阵里全是 0。其中“全是 0”的情况最容易被忽略但 heights 全为 0 时直方图函数会返回 0不需要额外特判这也是这个做法很干净的一个点。6. 换条路左右边界动态规划不用栈也能 O(mn)6.1 left 数组的含义与更新除了单调栈官方题解还有一种很漂亮的动态规划写法它不开栈而是维护三个一维数组height[j]、left[j]、right[j]。height[j]和前面一样是当前列的连续 1 高度。left[j]表示直方图里第 j 根柱子高度为 height[j]向左最多能扩到哪个下标也就是说它作为矩形的一部分时左边界。更新 left 时需要同时满足两个约束所以取 max上一行已经算出来的left[j]它代表了纵向的“历史限制”当前行从左往右看时正在延续的连续 1 段的起点cur_left它代表了横向的“本行限制”。遇到matrix[i][j] 0时height[j]归零left[j]也要重置为 0并且把cur_left更新成j 1。重置为 0 是因为这一列在当前行没有高度矩形不可能包含它cur_left前移则是为了下一段连续 1 重新计数。6.2 right 数组的反向扫描right[j]和left[j]镜像对称但它存的是开区间下标右边第一个“非法列”的位置。初始化right[j] n表示默认可以一直延伸到最右端。反向从右往左扫描维护一个cur_right遇到0就把cur_right更新成 j并把right[j]重置为 n遇到1就执行right[j] min(right[j], cur_right)。这里最容易糊涂的是为什么最后的宽度是right[j] - left[j]而不是right[j] - left[j] 1。因为 left 是闭区间左端点right 是开区间右端点两者相减正好是中间包含的列数。用示例矩阵第 3 行验证一下那一行 heights 是[3, 1, 3, 2, 2]left[3] 2right[3] 5宽度就是 3高度是 2得到面积 6和前面单调栈算出来的答案一致。6.3 完整 DP 代码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 left [0] * n right [n] * n best 0 for i in range(m): # 更新高度 for j in range(n): if matrix[i][j] 1: height[j] 1 else: height[j] 0 # 更新左边界 cur_left 0 for j in range(n): if matrix[i][j] 1: left[j] max(left[j], cur_left) else: left[j] 0 cur_left j 1 # 更新右边界反向扫描 cur_right n for j in range(n - 1, -1, -1): if matrix[i][j] 1: right[j] min(right[j], cur_right) else: right[j] n cur_right j # 结算当前行 for j in range(n): best max(best, height[j] * (right[j] - left[j])) return best6.4 三种解法的对比表方案时间复杂度空间复杂度特点行对枚举 前缀和O(m²n)O(mn)思路直观适合当暴力验证器逐行直方图 单调栈O(mn)O(n)标准最优解代码短推荐主用逐行直方图 左右边界 DPO(mn)O(n)不需要栈但要管理三个一维数组我个人更推荐主用单调栈版本因为它的思路在 84 里已经铺垫过迁移成本最低DP 版本当作“换一种视角”来理解就好它本质上也是在维护每根柱子的左右边界只是把“弹出时计算”换成了“每行扫描时递推”。7. 提交之前必须避开的坑以及我怎么用对拍定位 bug7.1 最容易翻车的四类错误第一类错误是字符和数字混淆。矩阵里存的是字符串1和0代码里如果写成matrix[i][j] 1Python 不会报错但永远为 False结果就是所有 heights 都是 0答案恒为 0。这种 bug 肉眼很难发现因为逻辑结构完全正确。第二类错误是忘了在0处把heights[j]清零。不复位的话柱子高度只会不停累加得到的一定是偏大的错误答案。第三类错误是空矩阵判断不完整not matrix过了但matrix[0]还可能越界所以if not matrix or not matrix[0]这两个条件一个都不能少。第四类错误是把这道题和 LeetCode 221 最大正方形混淆。221 因为限定正方形可以用 DP 记录边长85 要求的是任意宽高比的矩形必须用直方图或者等价的左右边界思路。7.2 哨兵 append 污染外层数组的老陷阱这题最经典的隐藏 bug 出在单调栈的哨兵实现上。如果 C 写成int largestRectangleArea(vectorint heights) { heights.push_back(0); // 直接改原数组 // ... }第一次调用后heights末尾多了一个 0下一次调用时又 push 一个 0数组会越变越长。虽然多出来的 0 本身不会产生正面积看起来“好像不影响结果”但数组无意义膨胀本身就是隐患而且一旦主函数后续依赖heights.size()做判断就会百思不得其解地出错。修法有两个一是改成按值传参让副本随便改二是在函数末尾pop_back()恢复原状。Python 里heights [0]会创建新列表天然规避了这个问题所以我给 Python 版本的注释里特意标了一句。7.3 调试手段手推、打印和暴力对拍我调这题的时候用了一条特别有效的组合拳。第一步是手推挑一个小的示例比如[2,1,5,6,2,3]在纸上把单调栈的每一步弹栈、入栈、left、right、width、area 都写出来确认自己理解的算法和标准答案一致。第二步是打印在主循环里每更新完一行 heights就print(heights)肉眼检查每一行的柱子高度是否符合预期。第三步也是最重要的一步写一个暴力解法做随机对拍。随机生成一批 6×6 的小矩阵同时跑 O(m²n) 的行对压缩解法和单调栈解法一旦结果不一致立刻打印矩阵定位问题。参考的比对框架大概长这样import random def maximalRectangle_brute(matrix): m, n len(matrix), len(matrix[0]) ans 0 for r1 in range(m): for r2 in range(r1, m): for c1 in range(n): for c2 in range(c1, n): ok all(matrix[r][c] 1 for r in range(r1, r2 1) for c in range(c1, c2 1)) if ok: ans max(ans, (r2 - r1 1) * (c2 - c1 1)) return ans # 随机跑 500 组 6x6 矩阵做对拍 for _ in range(500): mat [[1 if random.random() 0.5 else 0 for _ in range(6)] for _ in range(6)] a Solution().maximalRectangle(mat) b maximalRectangle_brute(mat) if a ! b: print(mismatch, mat, a, b) break else: print(all ok)我自己刷这题的实际经历是先写行对压缩版本当验证器然后用单调栈写完优化版最后靠随机对拍才意识到 C 里哨兵 append 会污染外层 heights。如果时间有限只想记住一个最重要的经验那就是二维矩阵题一定先写一个简单正确的暴力版本再拿它去对拍优化版。LeetCode 85 尤其适合这个流程因为你很难单凭肉眼看出直方图方法哪里写错了但随机数据会把每一个边界问题都毫不留情地暴露出来。