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在 index1右边第一个比它矮的高度是 2在 index4所以这个柱子能形成的最大矩形高度为 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(vectorvectorchar matrix) { if (matrix.empty() || matrix[0].empty()) return 0; int m matrix.size(), n matrix[0].size(); vectorint 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 vectorint heights) { int n heights.size(); vectorint 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 高度数组忘记清零导致虚高如果当前行的某个格子是0heights[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 4left 1那矩形从下标 2 到下标 3宽度是 2正好等于4 - 1 - 1。如果你发现面积算出来明显偏大或者测试样例差一点点大概率是这里符号或边界搞错了。建议用手推一个极小的例子比如heights [1,2]整个过程从 i0 到 i2 手动走一遍一遍就能校正。4.5 常见问题速查表症状原因解决方式结果一直为 0字符判断写成 1改为 1结果偏大高度数组遇到 0 没有清零补上else heights[j] 0结果偏小或缺失循环没走到i n的哨兵结束确保求柱状图时遍历到nPython 越界在largestRectangleArea里原地append(0)拷贝一份再加哨兵空矩阵报错忘了判空开头if (matrix.empty()) return 0;宽度算错忘记减掉 right 和 left 两个端点用公式right - left - 1验证我在实际刷题群里看到过好几个类似的求助多半是上面这些原因。这类问题最好的排查方式不是反复读代码而是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 题十分钟就写完了。如果你现在也卡在这里别硬刚回炉一维版把每个柱子的左右边界推导弄懂再回来看矩阵版本你会觉得这道题突然变得通透。刷算法题就是这样同一个模式反复出现第一次觉得玄乎第二次觉得眼熟第三次就是肌肉记忆了。