企业官网建设流程全解析

LeetCode 第 85 题“最大矩形”几乎是每一个刷单调栈专题的人都会撞上的一堵墙。初看题面，它只是把 84 题“柱状图中最大的矩形”从一根水平线拓展成一个二维棋盘，但真正动起手来，很多人却卡在“怎么把二维矩阵转换成一维问题”这一步。这道题之所以经典，就在于它逼着你把“降维压缩”和“单调栈”两个技巧同时用出来，一旦想明白，你会豁然开朗，后面再遇到类似的全 1 矩形、全 1 子矩阵计数，都能顺着同一套路秒掉。这篇博文不讲虚的，直接通过我的复现过程，把题目拆解、核心思路、完整代码、坑点排查全部摊开来讲，适合刚刷完 84 题想进阶的选手，也适合准备算法面试、周末想打 LeetCode 周赛前临时抱佛脚的朋友。

先给你一个结论：这道题的官方解法就是“对每一行做一次 84 题的柱状图最大矩形”，时间复杂度 O(mn)，空间复杂度 O(n)。如果你已经理解 84 题的单调栈写法，那 85 题只差一层“每一行滚动更新高度数组”的窗户纸；如果 84 题还不太熟，这篇也会把单调栈为什么能在线性时间内求出最大矩形讲清楚，让你一次弄懂两个题。

1. 从题面说起：最大矩形到底在问什么

1.1 题面拆解与隐藏信息

题目输入是一个二维矩阵，矩阵里只包含字符'0'和'1'，要求找出只包含'1'的最大矩形，并返回它的面积。注意几个关键的隐藏信息：

• 矩形必须是实心的，不能有 0 混在里面。这意味着如果某一列在某一行是 0，那这条“柱子”在这一行就到头了，不能继续往上累计。
• 面积是矩形面积，不是连通区域面积，所以两个中间隔着 0 的 1 区域不能拼在一起算。
• 矩阵的行和列都可能达到 200，是个不大不小的数据范围，既不允许 O(n^4) 级别的暴力枚举，也不需要过于极端的优化，普通 O(mn) 或 O(m^2 n) 都是可接受的。

我自己刷题时有个习惯：先看数据范围再决定算法方向。看到 200，第一反应就是要么 O(n^2) 枚举加前缀和，要么直接找线性做法。如果题目范围是 1000 或更大，暴力肯定过不了，尽早切换思路。

1.2 这题和 84 题“柱状图中最大的矩形”的血缘关系

LeetCode 84 题给你一个整数数组heights，其中每个元素代表一根柱子的高度，求这个柱状图中能够勾勒出的最大矩形面积。典型例子是heights = [2,1,5,6,2,3]，最大面积是 10。

这两题简直像是同一道题的两个版本：84 题的地基是“一排柱子”，85 题的地基是“二维矩阵”。如果我们把 85 题的矩阵从上往下逐行扫描，统计每一列从当前行往上连续出现了多少个 1，那么每一行都能得到一个“高度数组”，这个数组就等价于 84 题里的柱状图。换句话说，85 题就是“做若干次 84 题”，每次处理的柱状图高度不同。

很多题解会直接甩给你一句“用单调栈”，但如果你不知道这个压缩关系，就算背下了代码也记不住。我把这个转换过程看成是“把二维问题投影到一维”：每一行都相当于从底部往上看，把连续的 1 叠成柱子，0 的位置就当作地面。

1.3 先算一笔账：暴力为什么行不通

老一辈刷题选手遇到这种题第一反应肯定是枚举矩形：先枚举左上角(r1, c1)，再枚举右下角(r2, c2)，然后检查这个矩形里是不是全是 1。这个做法的复杂度是 O(m^2 n^2) 个矩形，每个矩形再花 O(mn) 去检查，整体高达 O(m^3 n^3)。就算用二维前缀和把“检查是否全 1”优化成 O(1)，枚举矩形本身仍然要 O(m^2 n^2)。

按题目最大规模 200×200 来算，200 的平方是 40000，两个方向枚举就是 1.6e9，这是单次检查不可能承受的量级；如果再乘上检查的时间，直接会跑到宇宙热寂。所以必须放弃“枚举矩形”，改成“枚举柱状图”，用单调栈把每一行压到 O(n)，最终整体 O(mn) 才能稳稳通过。

2. 思路拆解：从暴力到单调栈的递进

2.1 一维柱状图的最大矩形怎么求

在跳进二维之前，先把 84 题的一维问题彻底讲透。对于数组heights = [2,1,5,6,2,3]，我们可以对每一根柱子思考一个问题：如果这根柱子作为矩形的最低高度，那么矩形最远能往左右延伸到哪里？

答案取决于左右两边第一个比它矮的柱子位置。比如高度为 5 的柱子，它左边第一个比它矮的高度是 1（在 index=1），右边第一个比它矮的高度是 2（在 index=4），所以这个柱子能形成的最大矩形高度为 5，宽度为4 - 1 - 1 = 2，面积是 10。你可能会问，为什么跳过中间那个 6 不纳入？因为 6 比 5 高，矩形高度由最低的 5 决定，纳入更高柱子不影响；但再往右到 2 就会把高度拉低，所以必须止步于此。

给每根柱子都算一次左右边界，然后取面积最大值，就能得到整个柱状图的最大矩形。问题是怎么高效地找左右第一个比它矮的柱子。最朴素的办法是每个柱子往左右各扫一遍，整体 O(n^2)，对于 200 列勉强能跑，但如果列数到了 10^5 就废了。单调栈就是为这个问题量身定制的工具。

2.2 二维矩阵如何压成一维高度数组

这才是 85 题最核心的一步。我们定义一个数组heights，长度等于矩阵列数，初始全为 0。然后从第 0 行开始逐行扫描，每扫描到一行，就更新一次：

• 如果matrix[i][j] == '1'，那么heights[j] += 1，表示这列从当前行往上连续 1 的个数又多了一层；
• 如果matrix[i][j] == '0'，那么heights[j] = 0，表示这列在这里断掉了，之前的连续 1 全部作废。

拿官方示例来说，矩阵为：

1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0

处理完第 0 行后，heights = [1, 0, 1, 0, 0]；处理完第 1 行后，heights = [2, 0, 2, 1, 1]；处理完第 2 行后，heights = [3, 1, 3, 2, 2]；处理完第 3 行后，heights = [4, 0, 0, 3, 0]。

每一轮的heights都代表了一个柱状图，对它调用一次 84 题的解法，拿到当前行范围内的最大面积，全部行的最大值就是答案。这种滚动更新的方式很像动态规划里的“前缀状态”，但不需要额外二维数组，一行滚动数组就能搞定，空间省得很。

2.3 单调栈在一次遍历里到底做了什么

先说结论：单调栈能在 O(n) 时间内，对所有柱子一次算出“左侧第一个更矮位置”和“右侧第一个更矮位置”。

我们维护一个栈，栈里存的是柱子的下标，并且保证从栈底到栈顶，柱子高度严格递增。遍历到当前位置 i 时，如果当前高度比栈顶高度小，说明栈顶柱子找到了右侧第一个比它矮的柱子，也就是 i。此时弹出栈顶柱子 t，它的高度是heights[t]，左边界就是弹出后新的栈顶（如果栈空，说明左边没有更矮的，用 -1 当哨兵），右边界就是当前 i，宽度为i - left - 1，面积就是heights[t] * 宽度。

这里有一个很多人第一次看会懵的点：为什么弹出后的新栈顶就是左边界？因为栈是递增的，在 t 入栈之前，恰好有一个比 t 矮或相等的柱子被压在下面，它必然是 t 左边最近的更矮者。t 弹出后，新栈顶正是在 t 左侧还没被弹出的那个柱子，用它做左边界，宽度正好覆盖了所有高度不低于 t 的连续区域。想明白了这一点，单调栈就不再是死记硬背的模板了。

2.4 为什么用递增栈而不是递减栈

一个特别容易问的问题：单调栈分递增和递减两种，84 题和 85 题为什么非要递增栈？

因为我们要找的是“左右第一个更矮”的位置，所以栈底到栈顶从矮到高递增，才能保证：当新元素比栈顶矮时，栈顶元素的右边界出现，而栈顶左侧的元素一定比它矮，直接作为左边界。如果用递减栈，栈顶元素本身就是当前区间最高的，反而找不到“左侧第一个更矮”的信息。

这种选择本质上和题目需求互锁：找下一个更大元素用递减栈（比如 739 每日温度），找下一个更小元素用递增栈。85 题要找的是“下一步变矮”，所以递增栈。以后遇到“找左右边界”类题目，先想清楚边界条件是更大还是更小，再决定栈的方向。

3. 代码实现与细节打磨

3.1 C++ 完整实现与逐行注释

这道题实现层面最大的技巧是：在求每一行柱状图最大矩形的函数里，往末尾补一个高度为 0 的“哨兵柱”，这样循环结束后，栈里所有柱子都会被强制弹出，不需要再单独写一段收尾逻辑。

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 ans = 0; for (int i = 0; i < m; ++i) { // 更新每一列的高度：当前行是 '1' 就累加，是 '0' 就清零 for (int j = 0; j < n; ++j) { if (matrix[i][j] == '1') { heights[j] += 1; } else { heights[j] = 0; } } ans = max(ans, largestRectangleArea(heights)); } return ans; } private: int largestRectangleArea(const vector<int>& heights) { int n = heights.size(); vector<int> st; // 栈，存下标 int maxArea = 0; // 遍历到 i == n 时，用高度 0 当作哨兵，把栈里所有柱子清零 for (int i = 0; i <= n; ++i) { int curHeight = (i == n) ? 0 : heights[i]; // 当前柱子比栈顶柱子矮，栈顶柱子的右边界确定 while (!st.empty() && heights[st.back()] >= curHeight) { int h = heights[st.back()]; st.pop_back(); int left = st.empty() ? -1 : st.back(); int width = i - left - 1; maxArea = max(maxArea, h * width); } st.push_back(i); } return maxArea; } };

这段代码的关键点有三个。一是heights[st.back()] >= curHeight里的>=，它保证了相等高度的柱子也会被弹出，让面积计算以最后一个相同高度柱子为准，宽度能扩展到更远，不会漏解。二是弹出后left的取值：栈空时代表左边没有更矮的柱子，用-1能直接把宽度算成i，正好是从 0 到 i-1 的全部宽度。三是外层循环必须走到i == n，否则最后栈里还会残留递增序列，最大面积可能被漏掉。

3.2 Python 写法与一个容易踩的坑

Python 代码更贴近伪代码，但有一个坑我必须单独拎出来：如果你在图省事，直接把heights.append(0)塞进求柱状图的函数，那么每一行调用之后heights的长度都会增加 1，下一行更新时会出现列索引错位甚至越界。正确做法是在函数内部拷贝一份新的列表再加哨兵。

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 ans = 0 for i in range(m): for j in range(n): if matrix[i][j] == '1': heights[j] += 1 else: heights[j] = 0 ans = max(ans, self.largestRectangleArea(heights)) return ans def largestRectangleArea(self, heights: List[int]) -> int: # 拷贝一份，不要污染调用方的列表长度 heights = heights + [0] stack = [-1] # 直接用 -1 作为左边界哨兵 max_area = 0 for i in range(len(heights)): while heights[stack[-1]] > heights[i]: h = heights[stack.pop()] w = i - stack[-1] - 1 max_area = max(max_area, h * w) stack.append(i) return max_area

这里我用了stack = [-1]而不是判断stack是否为空，这样在while条件里永远不用特判栈空，因为高度为 0 的哨兵heights[-1]永远不可能大于任何非负高度，循环一定会在安全边界停止。这个技巧和 C++ 版本里的-1左边界是同一个数学思想，只是换了个写法。另外注意w = i - stack[-1] - 1，此时stack[-1]是弹出后的栈顶，也就是左边界的位置。

Python 的时间表现不会差，但要注意 LeetCode 的判题环境下，频繁调用self.largestRectangleArea会带来一点函数调用开销，不过 200×200 的数据量完全不用在乎，除非你打算拿它去跑超大矩阵。

3.3 手推官方示例，看答案 6 是怎么来的

光看代码可能还是太抽象，我用手推一遍官方示例。矩阵长这样：

1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0

第一行扫描后，heights = [1,0,1,0,0]，这时候柱状图里最大矩形面积是 1（两棵高度为 1 的柱子各自面积为 1）。第二行更新后，heights = [2,0,2,1,1]，最大面积是第 2 列（下标从 0 开始）的柱高 2，宽度 1，面积 2。第三行更新后，heights = [3,1,3,2,2]，这一轮你能看到第 0 列的柱子高度变成 3，面积 3；但最大的其实是下标 2、3、4 三根柱子，高度分别为 3、2、2，如果以高度 2 为基准，宽度可以扩到 3，面积是 6。官方答案的最大矩形就是原矩阵的第一行到第三行、第三列到第五列那块区域，高度 2、宽度 3，面积 6。第四行更新后，heights = [4,0,0,3,0]，最大面积是第 0 列的高度 4，面积也只有 4。所以全局最大是 6。

我每次写题解都喜欢手推一遍示例，因为这样能发现推导和代码之间的缝隙。第三行那一步，如果你只盯着最高的柱子 3 去看，会错过高度 2、跨度 3 的组合，而单调栈恰恰能把每个高度对应的最大宽度都算出来，不会漏掉这类“矮个子但占地面积大”的情况。

3.4 复杂度分析与空间占用

时间上，外层循环遍历 m 行，每行更新高度数组是 O(n)，每行调用一次单调栈也是 O(n)，所以总时间复杂度是 O(mn)。空间上，高度数组和单调栈都只和列数 n 有关，是 O(n)。这里 m 和 n 的位置不能搞反，因为是逐行扫，列数决定高度数组大小；如果矩阵转置，复杂度依然对称。

常规实现中，单调栈是一个动态数组，最坏情况下会压入 n 个下标，恰好等于列数。有人会担心largestRectangleArea里为了哨兵多遍历一次，是不是多花了 O(n)？严格说确实是 2n 的量级，但常数不影响渐进复杂度，在 LeetCode 判题中差距可以忽略。真要追求极致，也可以在循环结束后单独弹栈，不过那样代码会多一点分支，反而容易出错，我推荐哨兵写法。

4. 实战中的典型错误与排查技巧

4.1 字符类型和整数类型的隐形坑

在写 C++ 时，matrix的元素类型是char，判断当前格子是 1 必须写成matrix[i][j] == '1'，注意单引号不能省。如果不小心写成matrix[i][j] == 1，这个判断永远为假，因为'1'的 ASCII 码是 49，而不是 1，最后所有heights都会被清零，答案永远为 0。

Python 里也有类似问题：矩阵是字符串列表，取出来的是'1'这个字符串，所以判断要写matrix[i][j] == '1'，不能写== 1。这种低级错误非常隐蔽，因为它不报错，只是结果全错，而且你盯着逻辑看半天可能都反应不过来。排查办法很简单：写完后找一个全 1 的 1×1 矩阵[["1"]]测试，如果能返回 1，说明类型判断没问题。

4.2 高度数组忘记清零导致虚高

如果当前行的某个格子是'0'，heights[j]必须立刻归零，代表这一列到这里断掉了。我在第一次写这道题时，内部循环只写了if (matrix[i][j] == '1') heights[j]++;，忘了加else heights[j] = 0，结果上一行积累的高度被错误地带到下一行，导致很多不存在的矩形被算出来。

这一点初学者特别容易忽略，因为从直觉上看，“累加”才是重点，“清零”只是分支。但你想一下，因为底色是二维的，0 的位置就是一个“断层”，不清零的话，后面所有列的高度都会失真。我后来养成了一个习惯：所有滚动数组更新时，先写else分支再写主分支，强制自己考虑“断掉”的情况。

4.3 单调栈弹栈条件用大于还是大于等于

两种写法都能得到正确答案，但理解它们的差别很重要。用>弹栈时，高度相等的柱子不会互相弹出，每个柱子按自己的高度计算一次面积；由于高度相同，算出来的面积是一样的，只不过宽度可能不同，最终max结果不变。用>=弹栈时，相等的柱子会提前弹出，后一个柱子接管更宽的边界，计算时使用的宽度更大，同样不会漏解。

我推荐用>=，理由有两个：一是配合末尾 0 哨兵时，能保证所有柱子最终都被弹干净，代码逻辑更统一；二是在求全 1 矩形的变形题中，某些题目要求统计子矩形数量，用>和>=会得到不同的计数，提前养成习惯可以减少踩坑。

4.4 宽度计算为什么是 i - left - 1

很多新手会在这里懵住：已经弹出栈顶柱子了，为什么宽度不是i - 弹出的下标？因为弹出的柱子高度为 h，它右边第一个更矮的位置是 i，左边第一个更矮的位置是弹出后栈顶 left，所以矩形覆盖的下标范围是left + 1到i - 1，区间长度就是(i - 1) - (left + 1) + 1 = i - left - 1。

比如当前 i = 4，left = 1，那矩形从下标 2 到下标 3，宽度是 2，正好等于4 - 1 - 1。如果你发现面积算出来明显偏大，或者测试样例差一点点，大概率是这里符号或边界搞错了。建议用手推一个极小的例子，比如heights = [1,2]，整个过程从 i=0 到 i=2 手动走一遍，一遍就能校正。

4.5 常见问题速查表

我在实际刷题群里看到过好几个类似的求助，多半是上面这些原因。这类问题最好的排查方式不是反复读代码，而是print/输出每一行更新后的heights和每个面积，对照手推过程，问题会立刻暴露。

5. 从 85 题学会一类题：单调栈的泛化与刷题路线

5.1 84 题就是这题的前置课

强烈建议把 84 题和 85 题连着刷，顺序不要反。85 题的代码本质上是在 84 题外面套了一个行循环，如果你先理解了 84 题的单调栈原理，85 题就只剩下“每行更新高度数组”这一层新东西。相反，如果一上来直接啃 85 题，同时面对两个新概念，很容易被绕晕。

我当时刷题时的顺序是：先刷 84 题并写清楚一篇题解，把单调栈的左右边界推导彻底搞懂，再看到 85 题时几乎没花什么力气，最大矩形直接被拆成了“逐行调用 84 题”。这也是 LeetCode 热门 100 题里常见的一对“连续剧”题目，很多系统的算法题单都会把它们安排在一起。

5.2 和 42 接雨水、739 每日温度的对比

同样是单调栈，42 题“接雨水”和 85 题的解法长得有点像，但细节完全不同。接雨水是找到每个凹陷左右两侧更高的柱子，才能存住水，所以它用的是递减栈（栈底到栈顶从高到低），当前柱子比栈顶高时弹出并结算。85 题则是找左右更矮的柱子，所以用递增栈。一个找更高，一个找更矮，方向正好相反。

739 题“每日温度”也是找右边第一个更高温度的下标，用的是递减栈。我的经验是：不要试图背一套模板通吃，而是每次遇到题目，先问自己“我要找的是左边/右边第一个更大还是更小”，然后决定栈的单调方向，这才是真正的解题能力。把 84、42、739 三题放在一起对比，单调栈这个模块就基本吃透了。

5.3 221 最大正方形：为什么这道题不用单调栈

LeetCode 221 题“最大正方形”看起来和 85 题很像，但解法却用动态规划。原因是正方形对长宽有强约束，当右下角位置(i, j)作为正方形右下角时，边长由左上、上、左三个位置的最小值加 1 决定，可以逐格递推。而矩形没有边长相等的约束，不能用这么简单的 DP 状态转移，强行枚举矩形长宽会让状态维度爆炸，所以单调栈更合适。

这两题的对比很值得做：见到“最大正方形”想 DP，见到“最大矩形”想单调栈，这个区分本身就是算法面试的高频考点。记住这个规律，下次遇到同类问题时，你就能快速定位到正确的解法方向。

5.4 延伸变体和每日一题的正确打开方式

85 题的变体很多，最典型的是 LeetCode 1504 统计全为 1 的子矩形个数，它同样基于每行高度数组，但单调栈内部结算面积的逻辑要改成统计每个矩形作为“底部”的贡献次数。这类题一旦刷过 85 题，就能顺着相同思路推理出来。另外 LeetCode 每日一题偶尔也会安排这种矩阵压缩题，核心套路万变不离其宗。

至于 LeetCode 周赛和热题里经常出现的基本计算器、爱吃香蕉的狒狒等题目，它们虽然和 85 题不是同一类，但刷题方法论是相通的：基本计算器考的是栈处理表达式优先级，爱吃香蕉的狒狒考的是二分答案，85 题考的是单调栈加矩阵压缩。每天一道题，先把题目归类到“数据结构”或“算法思想”的框架里，再针对性练习，效率会高很多，比漫无目的地刷题有用得多。

最后说一点个人体会：我在初学这道题时，看了三遍题解都没看明白，后来发现最大的障碍不是单调栈，而是我没先做 84 题。于是退回 84 题手推了两张纸的柱状图过程，再回来做 85 题，十分钟就写完了。如果你现在也卡在这里，别硬刚，回炉一维版，把每个柱子的左右边界推导弄懂，再回来看矩阵版本，你会觉得这道题突然变得通透。刷算法题就是这样，同一个模式反复出现，第一次觉得玄乎，第二次觉得眼熟，第三次就是肌肉记忆了。