LeetCode 85 最大矩形题解：逐行直方图 + 单调栈全解析

刷 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(m+1)/2 × n(n+1)/2，当 m=n=200 时大约是 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 ans

2.3 为什么行对压缩依然不是终点

如果只是追求 AC，O(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] == '1'，heights[j]加 1；
• 如果matrix[i][j] == '0'，heights[j]直接归零。

归零那一步极其关键。0 意味着纵向的“连续性”在这里断掉了，之前攒了多少层都作废，因为任何跨过这个 0 的矩形底部都会缺一块。把归零理解成“地基塌了，柱子要重新盖”就很好记。

3.2 在示例矩阵上手工推一遍

用题目示例一行一行推，能得到下面这张表：

第四列“该行直方图的最大矩形面积”需要用到柱状图求最大矩形的算法，也就是 LeetCode 84。以第 2 行为例，[3, 1, 3, 2, 2]这个直方图里，高度为 2 的柱子从第 2 列延伸到第 4 列，能撑起一个 2×3=6 的矩形，正好就是答案。

3.3 为什么原题答案等于所有行直方图的最大值

这一步的等价性需要说清楚。假设矩阵里有一个以第 i 行为底边的全 1 矩形，宽 w、高 h，那么它覆盖的 w 列在i-h+1到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]：

记录到的最大面积是 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_area

5. 完整题解代码：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(vector<vector<char>>& matrix) { if (matrix.empty() || matrix[0].empty()) return 0; int m = matrix.size(), n = matrix[0].size(); vector<int> 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(vector<int> heights) { // 按值传参，内部 push_back 不污染外部 stack<int> 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] = 2，right[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 best

6.4 三种解法的对比表

我个人更推荐主用单调栈版本，因为它的思路在 84 里已经铺垫过，迁移成本最低；DP 版本当作“换一种视角”来理解就好，它本质上也是在维护每根柱子的左右边界，只是把“弹出时计算”换成了“每行扫描时递推”。

7. 提交之前必须避开的坑，以及我怎么用对拍定位 bug

7.1 最容易翻车的四类错误

第一类错误是字符和数字混淆。矩阵里存的是字符串'1'和'0'，代码里如果写成matrix[i][j] == 1，Python 不会报错但永远为 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(vector<int>& 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 尤其适合这个流程，因为你很难单凭肉眼看出直方图方法哪里写错了，但随机数据会把每一个边界问题都毫不留情地暴露出来。