LeetCode 85 这道题说它是单调栈专题里的一道“坎”一点也不过分。刷过 LeetCode 84 的朋友都知道柱状图中最大矩形怎么求但一上来就做 Maximal Rectangle很多人会愣住84 给的是现成的一维高度数组85 给的是一个二维 01 矩阵这俩怎么扯上关系的我自己第一次刷这道题的时候也花了不少时间才把“逐行构造高度数组”这个思路想明白想明白之后又发现真正写出 bug-free 的代码还有一堆细节要处理。这篇就把我的完整思考过程、推导方法、代码实现和踩过的坑一起整理出来希望能帮你把这道题彻底吃透。这道题在 LeetCode 热门 100 题里也占了一个位置周赛、面试里都算是高频考点。它不像“爱吃香蕉的狒狒”那种二分答案题思路只要点破就很简单85 题考察的是你能不能把一个二维问题“降维”成一个熟悉的一维问题再把一维问题的最优解法迁移过来这种能力才是刷题真正要练的东西。1. 题目理解与暴力思路1.1 题目到底在问什么给定一个rows x cols的二进制矩阵matrix里面的元素只有0和1要找出一个只包含1的矩形返回这个矩形的最大面积。注意几个关键细节矩阵元素是字符1和0不是整数 1 和 0。很多第一次写的人会在这里栽跟头拿if (matrix[i][j] 1)去判断结果永远进不去分支。矩形必须是完整包含在矩阵内部的不能跨越边界。矩形边界必须贴着矩阵的格线不能在一个格子里取半截。矩形可以退化成一个点也就是说最小面积至少是 1只要矩阵里有1。题目最经典的那个例子1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0最大矩形的答案是 6也就是第 2 行到第 3 行、第 2 列到第 4 列围出来的那个 2 行 3 列的全 1 区域。1.2 暴力解法能走多远拿到这种矩阵题最朴素的想法肯定是枚举所有可能的矩形。第一版暴力枚举左上角(r1, c1)和右下角(r2, c2)然后逐格检查这个矩形里是否全是1。矩形数量是 O(rows² × cols²)检查每个矩形又要 O(rows × cols)总复杂度直接到 O(rows³ × cols³)这种复杂度连小规模数据都跑不动直接放弃。第二版暴力还是枚举左上角但向右、向下动态扩展。具体来说固定左上角(r, c)之后用一个变量max_width记录当前行往右最多能延伸多远然后逐行往下扩展每扩展一行就更新一次可行宽度再用当前行高 × 当前最大公共宽度更新答案。这个办法能把单次扩展做到接近 O(rows × cols)所有起点枚举完是 O(rows² × cols²)虽然依然不是最优解但它能帮你建立一个很重要的直觉矩形面积 垂直方向的高度 × 水平方向的宽度如果能把高度信息预处理出来这个问题就会简化很多。1.3 一个关键的直觉暴力法里最花时间的部分是每次都要重新确认“这个区间里是不是全是 1”。如果能预先知道每一列从某个位置往上连续有多少个 1那么高度就变成现成的数据了。打个比方把矩阵想象成一排排的积木柱子。只看某一行以及它上面所有行每一列连续1的个数就是这一列柱子的高度。第一行就是一堆高度为 0 或 1 的柱子第二行在上一行的基础上继续累加一旦碰到0柱子高度就被“切断”重新归零。到这里问题就自然转化成了把每一行当成柱状图的“地面”求这个柱状图里的最大矩形面积再把所有行的结果取最大。柱子高度数组已经通过扫描矩阵得到了剩下的事情就是 LeetCode 84 题已经解决过的问题。2. 核心转化逐行构造高度数组2.1 高度数组的递推公式定义heights[j]为以当前处理到的行i为底边第j列往上连续1的个数。递推关系非常直观如果matrix[i][j] 1说明这一列当前行的格子是 1它可以接到上面已有的连续 1 后面所以heights[j] heights[j] 1也就是在上一行的高度基础上加 1。如果matrix[i][j] 0柱子断了这一列的高度直接归零heights[j] 0。注意上面公式左边的heights[j]是当前行的值右边的heights[j]是上一行的值。写代码的时候一般直接在原数组上累加因为先用后覆盖不会产生脏数据。2.2 用示例矩阵走一遍流程还是用题目给的经典矩阵第 0 行: 1 0 1 0 0 第 1 行: 1 0 1 1 1 第 2 行: 1 1 1 1 1 第 3 行: 1 0 0 1 0初始heights [0, 0, 0, 0, 0]。处理第 0 行后[1, 0, 1, 0, 0]。这一行的柱状图最大面积是 1随便取一个高度为 1 的柱子。处理第 1 行后第 0 列上面有(0,0)和(1,0)两个连续的 1所以高度是 2第 2 列两个连续 1高度 2第 3 列虽然当前行是 1但第 0 行对应位置是 0重新开始高度 1第 4 列同理高度 1。所以heights [2, 0, 2, 1, 1]。这个柱状图里能形成的最大矩形是哪个高度为 2 的柱子只有两个且不相邻不能横向合并高度为 1 的柱子从第 2 列到第 4 列是连续的宽度 3面积 1×33。所以第 1 行的答案是 3。处理第 2 行后第 0 列继续累加变成 3因为(0,0),(1,0),(2,0)都是 1第 1 列从 0 变成 1第 2 列变成 3第 3 列变成 2第 4 列变成 2。heights [3, 1, 3, 2, 2]。这个柱状图就厉害了最大的矩形是高度 2、宽度 3 的那块区域跨第 2、3、4 列面积 2×36正好对应题目答案。处理第 3 行后第 0 列变成 4第 1 列归零第 2 列归零第 3 列变成 3第 4 列归零。heights [4, 0, 0, 3, 0]。最大面积是 max(4, 3) 4不如之前的 6。最终答案就是所有行结果里的最大值 6。2.3 复杂度没有想象中那么高每一行求柱状图最大矩形如果使用 LeetCode 84 的单调栈解法单行是 O(cols)。总共有 rows 行所以整体复杂度是 O(rows × cols)。空间方面只需要一个heights数组和一个栈都是 O(cols)。这里要强调一点很多人潜意识里觉得“二维问题至少是 O(rows² × cols²) 起步”但其实通过逐行降维我们可以把问题拆成 rows 个一维子问题每个子问题线性解决整体就是线性乘法的复杂度跟元素总数成正比。这个“把二维拆成一维”的思路在矩阵类题目里非常常用后面还会遇到。3. 单调栈解法从 84 题迁移的关键3.1 先复习 84 题的核心原理LeetCode 84 题给了一个整数数组heights每个元素代表柱子的高度求这些柱子能组成的最大矩形面积。单调栈的经典做法是遍历每个柱子对每个柱子heights[i]找到左边第一个比它矮的柱子位置left以及右边第一个比它矮的柱子位置right。那么以heights[i]为高度、能向左右扩展的最大宽度就是right - left - 1面积是heights[i] * (right - left - 1)。对每个柱子都算一遍取最大值。为什么找“比它矮”的柱子因为矩形要完整包含在柱子内部一旦遇到比自己矮的柱子再往左右扩展矩形的高度就无法维持原状了宽度再大也没有意义。单调栈是怎么高效找到左右边界的维护一个单调递增栈栈里存的是柱子的下标保证下标对应的柱子高度从栈底到栈顶是递增的。遍历到当前位置i时如果当前柱子的高度小于等于栈顶柱子高度说明栈顶柱子的“右边界”已经出现就是当前位置i而它的“左边界”就是栈内它下面的那个元素。此时就可以弹出栈顶结算以它高度为基准的矩形面积。这个过程每个元素最多入栈一次、出栈一次所以是 O(n)。3.2 哨兵技巧让边界处理更优雅上面描述的算法遍历完所有柱子后栈里可能还有剩余元素没有结算。比如最后一根柱子高度特别高它没有遇到更矮的右边界那它的右边界实际上是n数组末尾之外。处理起来要额外加一层循环代码容易写乱。一个常用的技巧是在heights数组的首尾各插入一个高度为 0 的哨兵。首部插入 0保证栈永远不会为空省去“栈空”判断尾部插入 0保证所有柱子都会在某个时刻被弹出并结算不需要收尾循环。加了哨兵之后栈里初始放入下标 0对应哨兵高度 0遍历时从下标 1 开始到最后遇到比栈顶矮的柱子就弹出结算。代码逻辑变得非常统一。3.3 Python 实现柱状图最大矩形先把这个 84 题的核心函数写出来后面直接复用def largestRectangleArea(heights: List[int]) - int: # 加哨兵避免特判栈空和收尾 heights [0] heights [0] stack [0] max_area 0 for i in range(1, len(heights)): # 当前柱子比栈顶矮说明栈顶的右边界已经出现 while heights[i] heights[stack[-1]]: h heights[stack.pop()] left stack[-1] # 栈内前一个元素就是左边界 right i # 当前遍历位置就是右边界 max_area max(max_area, h * (right - left - 1)) stack.append(i) return max_area这里有几个关键点需要解释while条件是heights[i] heights[stack[-1]]也可以用。两者的区别在于遇到相等高度时是否提前弹出。用会把相等高度的柱子留在栈里后弹出的那个柱子结算的面积是准确的因为左右边界能正确包住所有相等高度的柱子用则会让前一个先弹出结果一样但代码处理边界时略有不同。我用的是配合哨兵写起来最不容易出错。弹出时right是当前遍历到的下标i不是i-1。因为区间(left, right)的左开右开区间长度是right - left - 1正好是左边界右侧第一根柱子到右边界左侧最后一根柱子的距离。3.4 把 84 题套进 85 题有了largestRectangleArea函数85 题的代码瞬间就清晰了class Solution: def maximalRectangle(self, matrix: List[List[str]]) - int: if not matrix or not matrix[0]: return 0 rows, cols len(matrix), len(matrix[0]) heights [0] * cols max_area 0 for i in range(rows): # 逐行更新高度数组 for j in range(cols): if matrix[i][j] 1: heights[j] 1 else: heights[j] 0 # 对当前行求柱状图最大矩形面积 max_area max(max_area, self.largestRectangleArea(heights)) return max_area这段代码非常短但它把二维问题完整地解决了。重点在于理解largestRectangleArea内部每次都会在一个新的heights 数组上操作而heights在每一行之间是持续累加或清零的。有一点需要特别提醒largestRectangleArea里我给 heights 加了哨兵这其实是在原数组上做拼接。如果直接传入heights并修改它下一行还会用到这个数组但拼接后的数组长度变了后续更新 heights 的下标就全乱了。所以要么像我上面代码里写的在函数内部用[0] heights [0]生成一个新列表要么避免修改原数组。很多人在这个细节上踩坑我刚开始写的时候也在这里吃过亏。4. 完整代码与实现细节4.1 一个不用额外函数的合并写法如果你的面试官不喜欢函数套函数想把逻辑写在一个方法里也可以这样写class Solution: def maximalRectangle(self, matrix: List[List[str]]) - int: if not matrix or not matrix[0]: return 0 rows, cols len(matrix), len(matrix[0]) heights [0] * cols max_area 0 for i in range(rows): # 更新 heights for j in range(cols): heights[j] heights[j] 1 if matrix[i][j] 1 else 0 # 单调栈求当前柱状图最大矩形 # 加哨兵 h [0] heights [0] stack [0] for k in range(1, len(h)): while h[k] h[stack[-1]]: cur_h h[stack.pop()] left stack[-1] right k max_area max(max_area, cur_h * (right - left - 1)) stack.append(k) return max_area这个写法没有额外定义子函数逻辑上是等价的。注意每次循环都新构造一个h所以heights本身不会被污染下一行还能继续用。4.2 空矩阵与边界条件处理代码第一行就写了if not matrix or not matrix[0]。不要小看这一句它同时处理了“矩阵为空”和“矩阵只有 0 行但有列信息”的情况。LeetCode 的测试用例里matrix []和matrix []都可能出现。第二种情况里matrix[0]是空字符串但matrix本身不为空所以只判断not matrix是不够的必须再判断not matrix[0]。4.3 字符与数字的陷阱matrix[i][j] 1千万不能写成matrix[i][j] 1。因为矩阵元素是字符串1和0不是整数。虽然 Python 里1 1结果是 False但不会报错只会让你所有判断都失效然后得到结果 0。这种坑在 C 和 Java 里同样存在输入是vectorvectorchar或char[][]一定要看清楚类型。4.4 复杂度与空间分析时间复杂度很好算外层循环 rows 次内层更新 heights 是 O(cols)单调栈部分也是 O(cols)所以总时间复杂度 O(rows × cols)。空间复杂度heights数组 O(cols)单调栈最多也是 O(cols)总体 O(cols)。如果算上每次拼接出来的h其实也是 O(cols)。这个空间开销可以忽略不计。如果把largestRectangleArea写成一个独立函数每次传入heights那么要注意 Python 的列表是可变的如果你在函数里执行了heights.insert(0, 0)或者heights.append(0)这个修改会影响到调用方的列表。建议用[0] heights [0]这种生成新列表的方式或者干脆把哨兵逻辑写在主函数里。5. 常见问题与调试实录5.1 为什么结果总是偏小这是我调试时遇到的第一个问题。代码看起来没问题但跑样例矩阵返回的是 5 而不是 6。排查之后发现问题出在单调栈的边界计算上。我当时写的是while h[k] h[stack[-1]]: h_cur h[stack.pop()] left stack[-1] right k - 1 area h_cur * (right - left)这里的错误在于right取成k-1然后宽度又算成right - left。假设左边界下标是 1右边界下标是 5那么实际宽度应该是5 - 1 - 1 3柱子下标 2, 3, 4。如果我取right 4即 k-1再算right - left 4 - 1 3碰巧能得到一样的结果。但这是建立在右边界索引恰好比实际边界小 1 的前提下的一旦栈里有多个元素连续弹出这个公式就会算错。正确的理解方式是左边界是栈内前一个元素它指向的是左边第一个比当前弹出元素矮的柱子右边界是当前遍历到的位置 k它指向的是右边第一个比当前弹出元素矮的柱子。两者的开区间宽度是k - stack[-1] - 1。不要再去减 1 或者做别的变形。5.2 每行高度为什么会被上上行的数据污染正常情况下heights数组应该只反映“以当前行为底边向上连续 1 的个数”。如果某一行遇到0对应列的高度必须归零。我曾经在更新高度时写过这样的代码if matrix[i][j] 1: heights[j] 1 # 漏掉了 else 分支没有把 heights[j] 清零然后第二行跑出来的结果就全错了。第二列在第一行明明是 0但因为没清零第二行这里如果遇到 1会错误地累加成 2实际上应该从 0 重新开始。这个 else 分支非常关键它本质上是在模拟“柱子断了”的情况。缺了它整个推导就不成立了。5.3 栈为什么最后还会残留元素如果你写的是不带哨兵的版本遍历完所有柱子后栈里通常还会剩下一些高度递增的柱子。这些柱子一直没遇到更矮的右边界所以没被弹出。比如heights [2, 3, 4]遍历结束后栈里存了[0, 1, 2]三个下标它们的面积一个都没结算。这时候需要在循环结束后手动把栈里剩余元素依次弹出并计算面积。处理方式有两种在遍历结束后加一个while stack:循环把栈顶弹出左边界是新的栈顶右边界设为len(heights)。更推荐的方式是加尾部哨兵 0。因为 0 一定比所有柱子矮遍历到它时前面的所有柱子都会被弹出并结算循环结束后栈里只剩哨兵自己不需要额外逻辑。我强烈建议用哨兵写法。我一开始坚持不用哨兵觉得“应该能处理”结果每个版本都漏掉一些边界情况最后老老实实加了 0代码立刻干净很多。5.4 为什么用stack [0]而不是空栈加了首部哨兵后h[0] 0而栈里存的是下标所以初始栈应该包含下标 0。如果不放这个初始值当弹出第一个元素时stack[-1]会报 IndexError。当然你也可以在弹出后判断if stack:但每次结算都要做判断麻烦且容易遗漏。哨兵的本质就是用冗余数据换取代码的简洁和正确性。5.5 实际调试过程用一维数组跑一遍假设某一行更新完heights [2, 1, 5, 6, 2, 3]加哨兵后为[0, 2, 1, 5, 6, 2, 3, 0]。k1h[1]2栈[0]2 0入栈。栈[0,1]k2h[2]11 2弹出下标 1高度 2。此时 left0right2面积2*(2-0-1)2。然后 1 0入栈。栈[0,2]k3h[3]5入栈。栈[0,2,3]k4h[4]6入栈。栈[0,2,3,4]k5h[5]22 6弹出下标 4高度 6。left3right5面积6*(5-3-1)62 5弹出下标 3高度 5。left2right5面积5*(5-2-1)102 1停止弹出入栈。栈[0,2,5]k6h[6]3入栈。栈[0,2,5,6]k7h[7]00 3弹出下标 6高度 3。left5right7面积3*(7-5-1)30 2弹出下标 5高度 2。left2right7面积2*(7-2-1)80 1弹出下标 2高度 1。left0right7面积1*(7-0-1)6最大面积是 10这与[2, 1, 5, 6, 2, 3]的正确答案一致5 和 6 两个柱子组成 5×2 的矩形。这个手动模拟过程建议你也自己推一遍。只有亲手把每个弹出节点、左右边界算清楚才能真正理解单调栈的结算时机的来龙去脉。5.6 常见问题速查表症状可能原因解决办法返回 0把字符1当成整数 1 判断改成matrix[i][j] 1结果偏小单调栈右边界取成k-1右边界就是k宽度k - left - 1结果偏大高度数组没有在0处清零更新 heights 时补上 else 分支弹出时报 IndexError栈为空时访问stack[-1]使用首部哨兵 0初始栈[0]矩阵为空报错只判断了not matrix加上not matrix[0]结果和预期差一点点没有处理遍历结束后的残留栈使用尾部哨兵 06. 复盘与扩展这道题值回票价的地方6.1 一个更“取巧”的动态规划思路备选单调栈是这道题的标准解法但如果你觉得一下子理解起来有难度可以先试试动态规划版本的思路对每个格子(i, j)记录它的高度height[i][j]表示当前列往上连续 1 的个数。然后对于每个以该格子为底边的可能高度向左向右扩展找到满足高度条件的最大宽度再计算面积。这种方法不需要单调栈但最坏情况下每行每个位置都要向左向右扫描复杂度会达到 O(rows × cols²)。不过它比暴力法好理解适合作为过渡。真正追求最优解还是用单调栈。6.2 与相似题目的横向对比LeetCode 84、85、221、1273 这类题目放在一起看很有意思。84 题只给一维数组是单调栈的入门题。85 题在 84 的基础上套了一层矩阵本质是多次调用 84。221 题最大正方形可以用动态规划做也可以用 85 的思路只要把面积限制成“宽等于高”的正方形即可。1273 题虽然名字看起来像是矩阵题但实际上涉及的是树结构删除节点的统计跟 85 没有直接关系刷题时不要被题目编号的顺序带偏节奏。另外LeetCode 周赛里也经常出现“逐行/逐列处理”的题目核心思想就是先预处理前缀信息再转化成一维问题求解。学完 85 题你等于掌握了一个通用的二维问题降维套路。6.3 我的实际刷题顺序建议如果你还没把 84 题吃透直接做 85 题很容易卡住。我个人的建议顺序是先把 84 题的暴力版写一遍哪怕 O(n²) 也行目的是理解“每个柱子能往左右扩展多远”这个几何含义。再用单调栈写一遍 84 题体会栈的出入栈时机和面积结算时机。最后才做 85 题先想明白 heights 怎么逐行更新再套用 84 题的代码。写完 85 题后试着手动模拟几行矩阵验证高度数组的更新过程。这样一层一层递进比直接死磕 85 题要高效很多。我当初就是因为跳过 84 直接刷 85结果浪费了很多时间在本来已经解决过的问题上。6.4 一个锦上添花的优化滚动数组上面的写法里heights是动态更新的这个本质上已经是一个滚动数组了。你不需要真的开一个rows × cols的二维数组来装高度因为每一行只依赖上一行的高度存一维就够了。这样空间复杂度保持在 O(cols)也是这道题一个考察点是否能看出“高度”只需要滚动维护。如果你在代码里写了一个height [[0] * cols for _ in range(rows)]虽然也能跑通但空间上就浪费了。面试时如果被问到“能不能优化空间”其实就指向这个点。6.5 踩过这些坑之后的碎碎念回过头看85 题最难的其实不是单调栈本身而在于“为什么要用柱状图”这一步转化。很多人卡在这里是因为一直在想怎么直接在二维矩阵上找矩形而没有意识到可以把矩阵的每一行当成一维数组的 ground truth。我自己的体会是刷算法题不要急着看答案先用暴力法跑通一个朴素思路然后从暴力的瓶颈出发看哪些信息是可以预处理的。85 题的暴力瓶颈在于反复确认“矩形是否全 1”于是自然会想到把“向上连续 1 的个数”预处理好再交给柱状图算法处理。这个思维过程比最终那十几行代码值钱得多。最后再分享一个小经验写单调栈的时候如果你觉得某个边界条件特别绕大概率是哨兵没加对。首尾各补一个 0几乎能让所有边界问题消失。记住这一点以后遇到任何单调栈题目都能省掉一半的调试时间。