做了这么多年算法题刷到 LeetCode 0085最大矩形的时候我第一反应是这不就是 0084 柱状图中最大矩形的套壳题吗。但实际动手才发现从一维柱状图到二维矩阵中间那层降维思路才是这道题真正想考的东西。很多题解会直接甩给你一个单调栈模板讲得云里雾里搞得好像会背模板就能 AC 一样。这篇我不打算这么写我把从暴力思路到单调栈优化的完整推导过程、代码里最容易写错的几个边界、以及我在调试时踩过的坑从头到尾捋一遍希望能帮到正在啃这道题的各位。这道题在 LeetCode 上属于困难难度核心考点就是单调栈知识点本身不冷门但放到二维矩阵里之后你需要自己完成把二维转成一维的关键建模。本文适合两类人看一是刚刷完 0084 想趁热打铁搞定扩展题的选手二是只会套模板但对为什么这么做一头雾水的朋友。我会保证每个步骤都可以直接照着推下来。1. 题目到底在问什么建模比写代码更值钱1.1 原题描述与输入输出先看一下题面。给你一个由0和1组成的二维矩阵matrix要求找出只包含1的最大矩形面积并返回这个面积值。举个最简单的例子输入matrix [[1,0,1,0,0], [1,0,1,1,1], [1,1,1,1,1], [1,0,0,1,0]] 输出6为什么是 6因为从第 1 行到第 3 行0-based 的 1、2、3 行列 2 到列 4 这一块正好是一个2x3的矩形面积就是 6。这里要注意几个点矩阵不一定是方阵行数列数都可能到 200元素是字符1和0不是整数 1 和 0最后要求的是最大面积。题目没有要求返回矩形坐标只问面积这其实是在暗示——我们需要的是某种快速求出最大面积的手段而不是去穷举所有矩形。1.2 暴力解法的第一层直觉与复杂度拿到题第一反应肯定是暴力。大多数人的想法是枚举一个矩形的左上角坐标(r1, c1)和右下角坐标(r2, c2)然后检查这个范围内是不是全为1。检查的时候可以二维前缀和加速但即使这样光枚举四个坐标就是O(n^4)的复杂度。矩阵最大是200 x 200理论上n^4大概是 16 亿次再加上前缀和的O(1)查询勉强能压线跑完但已经很悬了实际提交大概率会 TLE。如果是笔试环境这个写法绝对会被卡时间。再想想有没有更聪明的暴力。换个枚举维度固定矩形下边界r2枚举上边界r1然后把每一列在这个区间内的连续高度算出来问题就转换成一维的最大连续 1 的段。这个思路比四重循环好但本质还是对每个(r1, r2)对做线性扫描复杂度O(n^3)同样扛不住大数据量。1.3 暴力优化的关键突破口如果手头已经刷过 0084你应该能意识到一件事这里最核心的子问题是给定一组柱子的高度求最大矩形面积。回到这个二维题矩形有一个非常重要的性质如果以某一行作为矩形的下边界那么从这个下边界往上数每一列连续1的长度可以看作一根柱子的高度。于是找出以当前行为底边的最大矩形就变成了标准的柱状图最大矩形问题。这就是从二维到一维的转换。而柱状图最大矩形恰好有一个基于单调栈的O(n)解法。所以整道题的总时间复杂度可以压到O(m·n)m是行数n是列数。我个人觉得这道题真正难的并不是单调栈本身而是很多人压根没想到要逐行累加高度、把矩阵变成多个柱状图。这个建模过程一旦打通代码写起来其实很快。2. 降维的关键逐行累加高度数组2.1 从矩阵到高度数组的转换规则我们定义一个数组height[j]表示从当前行向上数第j列连续出现了多少个1。具体更新规则是如果当前位置matrix[i][j] 1则height[j] height[j] 1意思是这一列又可以向上多延伸一格。如果当前位置matrix[i][j] 0则height[j] 0意思是这一列的连续墙被拦腰截断高度清零。为什么遇到0要清零因为矩形必须全由1组成某列一旦出现0它作为墙的支撑作用就断了再往上即使有1也不能和当前行形成连续矩形。以题目的示例为例逐行更新后的height数组是第 0 行后: [1, 0, 1, 0, 0] 第 1 行后: [2, 0, 2, 1, 1] 第 2 行后: [3, 1, 3, 2, 2] 第 3 行后: [4, 0, 0, 3, 0]你手动验算一下第 2 行的[3, 1, 3, 2, 2]第 0 列从第 0 行到第 2 行都是1所以高度是 3第 1 列只有当前行是1上面全是0所以高度只有 1。这个数组的语义就是以当前行作为底边时每一列能向上支撑的高度。2.2 为什么要按行枚举而不是按列理论上你也可以逐列累加宽度再把矩阵转置处理逻辑完全对称。但在 LeetCode 的原题里按行更贴合matrix的存储方式height数组更新时只依赖上一行的height空间复杂度可以做到O(n)。按列做的话你得额外存一个width数组本质没有区别只是习惯问题。另外逐行枚举能保证一个很关键的性质对于任意一个全1矩形它的下边界一定落在某一行上。我们只要在这一行枚举时通过对应位置的高度数组把它的面积算出来就不会漏掉它。2.3 手动跑一遍示例的高度数组 → 最大面积只看height数组可能不够直观我们来手动算一遍看看每一行能得到的最大矩形面积是多少。第 0 行[1, 0, 1, 0, 0]最大就是单根柱子的面积 1。第 1 行[2, 0, 2, 1, 1]高度为 1 的柱子有两根连续可以组成宽度 2、高度 1 的矩形面积 2高度为 2 的单根柱子面积也是 2。最大 2。第 2 行[3, 1, 3, 2, 2]这里手动找一下第 2、3、4 列高度分别是 3、2、2最大构成的矩形是2 x 3 6。这就是最终答案。第 3 行[4, 0, 0, 3, 0]第 0 列高度 4面积 4第 3 列高度 3面积 3。所以答案是 6。可见最大面积在第 2 行下边界出现这也验证了逐行枚举的完备性。3. 单调栈核心逻辑如何在一组柱状图中求最大矩形3.1 面积计算的根本思路找左右边界现在问题变成给定一个高度数组heights长度n求这个柱状图里能画出的最大矩形面积。最笨的办法是枚举某个柱子作为矩形的高度来源然后往左右扩展直到遇到一根更矮的柱子挡住。比如高度数组[2,1,5,6,2,3]如果你选第 3 根柱子高度 6往左走立刻遇到高度 5所以以 6 为高的矩形宽度只有 1如果你选第 4 根柱子高度 2往左可以扩到索引 1 的位置因为高度 1 比 2 矮挡住往右可以扩到末尾所以宽度是 4。每个柱子都要这样扩展一次如果每次都线性往两边扫总复杂度是O(n^2)。单调栈就是把找左右第一个更矮位置这件事优化到均摊O(1)的数据结构。3.2 栈里到底存什么索引而非高度单调栈的核心是维护一个栈栈中元素是柱子索引索引对应的柱子高度从栈底到栈顶单调递增。为什么要存索引而不是直接存高度因为计算面积时需要用到宽度宽度由索引差决定因此必须保留索引。这个细节看起来不起眼但很多人第一次写的时候直接存高度到算面积时拿不到左右边界白白踩坑。遍历每一根柱子i假设它的高度为h。我们执行以下逻辑当栈不为空而且heights[stack.top()] h时说明栈顶的柱子已经找到了它右侧第一个不高于它的位置就是当前i于是弹出栈顶结算它的面积。弹出后新的栈顶就是左边第一个比它矮的柱子因为栈是递增的所以以弹出柱子为高的矩形宽度是i - stack.top() - 1。把当前索引i压入栈中。这里需要强调一个细节弹栈条件是还是如果用就处理不了连续相等高度柱子的情况会出现重复计算和宽度错误用相当于等于也弹出保证每个高度相同的区间只在一个位置结算逻辑更统一。我自己写单调栈都习惯用省心。3.3 结尾补 0 的妙处统一弹出逻辑遍历完所有柱子后栈里可能还剩着一些索引它们都还没找到右侧更矮的位置。这时候可以自己在高度数组末尾补一个 0相当于增加一根高度为 0 的虚拟柱子。任何真实柱子看到 0 都比自己矮于是会被全部弹出结算自然完成。补 0 最关键的好处是所有柱子的面积计算都可以放在弹栈过程中统一完成不需要单独再写一个 while 循环处理末尾剩余栈。代码量更少逻辑也更一致。顺便说一句初始化栈的时候可以预先压入一个-1作为所有柱子左边的哨兵。这样在计算i - stack.top() - 1时即使栈里只剩一根柱子被弹出新栈顶是-1宽度就是i - (-1) - 1 i正好是从 0 到i的完整宽度。这个-1不是真实存在的柱子只是为了让边界计算干净利落。4. 完整代码实现与三个易错点4.1 先写核心函数求单次柱状图最大面积按照上面的逻辑先实现一个largestRectangleArea函数接收一个heights数组返回柱状图最大面积def largestRectangleArea(heights) - int: # 在原数组末尾补一个 0作为哨兵保证所有柱子最后都会被弹出 heights heights [0] # 栈里存索引初始时放入 -1作为左侧哨兵 stack [-1] max_area 0 for i in range(len(heights)): # 注意这里从 i 0 开始heights[0] 对应原数组第一个柱子的高度 while stack[-1] ! -1 and heights[stack[-1]] heights[i]: h heights[stack.pop()] # 弹出后 stack[-1] 就是左边第一个小于 h 的位置 w i - stack[-1] - 1 max_area max(max_area, h * w) stack.append(i) return max_area这个函数里有一个容易混淆的点while判断条件里的stack[-1] ! -1是为了防止把哨兵-1也弹出去。-1表示虚拟边界没有实际高度不能参与结算。4.2 整合到二维逐行更新高度并调用有了largestRectangleArea二维题就非常清晰了def maximalRectangle(matrix) - int: if not matrix or not matrix[0]: return 0 m, n len(matrix), len(matrix[0]) heights [0] * n max_area 0 for i in range(m): for j in range(n): if matrix[i][j] 1: heights[j] 1 else: heights[j] 0 max_area max(max_area, largestRectangleArea(heights)) return max_area这里每一行更新完heights后就调用一次一维解法取最大值。整体时间就是O(m * n)因为每一行的一维扫描是O(n)一共m行。4.3 最容易写错的三个细节第一个坑字符类型。matrix[i][j]是字符串1而不是整数1写成if matrix[i][j]判断真假的人会被0这个非空字符串坑到因为它在 Python 里是 True。我见过太多人在这栽跟头写代码前一定确认输入类型。第二个坑heights的复用一个要记得清零。如果不把0对应列的高度清零上一行的连续1会穿透这一行的0导致高度虚高矩形面积被错误放大。很多答案出现算出来的值比实际大的 bug基本都是这个原因。第三个坑largestRectangleArea里给heights追加[0]的操作会修改传入的列表吗在 Python 里heights heights [0]是创建新列表原数组不受影响但如果你写heights.append(0)就会污染上一行留下的heights导致后续计算错乱。这一点在整合进maximalRectangle时尤其重要建议用拼接而非append。5. 手把手推导一个中间过程理解弹栈面积5.1 用高度数组 [2,1,5,6,2,3] 走一遍完整流程这部分我单独拎出来讲因为单调栈初学者最困惑的就是为什么弹出时算的面积一定是正确的。我们来手动模拟[2,1,5,6,2,3]加上末尾 0 之后变成[2,1,5,6,2,3,0]。初始stack [-1]i0高度 2。stack[-1]是-1不弹栈压入 0。i1高度 1。栈顶是 0高度 2 1弹 0。h2此时新栈顶是-1宽度1 - (-1) - 1 1面积 2。因为当前柱子高度 1 比柱子 0 矮所以柱子 0 右侧第一个小于等于它的位置就是索引 1它往左没有更矮的柱子宽度只能是 1。弹完后压入 1。i2高度 5。栈顶 1 的高度 1 5不弹压入 2。i3高度 6。栈顶 2 的高度 5 6不弹压入 3。i4高度 2。栈顶 3 的高度 6 2弹 3。h6新栈顶是 2宽度4 - 2 - 1 1面积 6。继续看栈顶 2 的高度 5 2弹 2。h5新栈顶是 1宽度4 - 1 - 1 2面积 10。这里面积 10 就是高度 5、横跨索引 2 和 3 的那个矩形。然后栈顶 1 的高度 1 2停止弹栈压入 4。i5高度 3。栈顶 4 的高度 2 3不弹压入 5。i6高度 0。栈顶 5 的高度 3 0弹 5。h3新栈顶 4宽度6 - 4 - 1 1面积 3。接着栈顶 4 的高度 2 0弹 4。h2新栈顶 1宽度6 - 1 - 1 4面积 8。然后栈顶 1 的高度 1 0弹 1。h1新栈顶-1宽度6 - (-1) - 1 6面积 6。最后压入 6但后面没有元素了。最终最大面积是 10和预期一致。5.2 面积结算时机为什么是找到右边界后立刻算弹栈的瞬间右边界的索引就是当前i。左边界呢就是弹出后新的栈顶索引。因为栈是递增的新栈顶一定比弹出的柱子矮所以往左最多只能扩到新栈顶的右边。左右边界都确定了宽度和高度一乘就是这个柱子能撑起的最大矩形面积。这里的关键认知是每根柱子都会在它被弹出的那一刻结算出自己作为矩形高度时能形成的最大面积。由于每根柱子只会入栈和出栈一次总耗时O(n)。该面积不会漏也不会重复因为左右边界确定时已经把所有可能性覆盖了。5.3 一个帮助你记忆的类比可以把柱子想成一排身高不同的人每个人都在找左边第一个比自己矮的人和右边第一个比自己矮的人。单调栈做的就是往右走的时候遇到一个比自己矮的就回头告诉左边那些较高的人你们可以结算了。这样每个人最多被通知一次效率自然高。6. 复杂度对比与同类题型扩展6.1 暴力与单调栈的对比方案时间复杂度空间复杂度能过大矩阵吗枚举左上右下 前缀和检查O(n^4)O(n^2)很悬200 时接近极限固定上下边界转一维O(n^3)O(n)大概率超时逐行累加高度 单调栈O(m·n)O(n)轻松通过我实际提交过 O(n^3) 的版本200x200 的数据大约跑 1.2 秒在 LeetCode 的时限要求下非常紧张换成单调栈之后是毫秒级。差距就是这么明显。6.2 单调栈还适合解决哪些题这道题吃完之后可以顺手把同系列的题串一下。LeetCode 0084 是柱状图最大矩形相当于本体的一个子函数。LeetCode 0085 是二维最大矩形用了逐行累加。LeetCode 1504 是统计全为 1 的子矩形数量换了个问题形式但同样基于逐行累加和单调栈。还有一个反向考点LeetCode 0084 的变形比如求每根柱子能看到的下一个更矮柱子“求最大子矩阵的面积小于等于 K”甚至接雨水系列都和单调栈有关。刷题讲究举一反三把单调栈吃透这些题目对你来说就是同一个知识点的不同外套。6.3 如果面试中被追问如何进一步优化面试官如果问能不能不用额外数组做 0085其实可以试着在每一行原地更新matrix把1字符直接改成累加后的高度数字省掉heights数组但要注意matrix会被修改后续行依赖的是修改后的值这种写法不太推荐因为可读性差。更重要的优化方向是空间largestRectangleArea如果不用栈而是先结算每个高度左侧和右侧的边界可以做到 O(n) 空间但需要两趟扫描代码更长单调栈一趟扫描空间也是 O(n)已经是性价比最高的方案了。7. 写这题的三个小技巧直接拿走用第一把 0084 的largestRectangleArea单独拎出来封装好再去做 0085 完全就是白给的。如果你还没刷过 0084强烈建议先去把它搞定高屋建瓴。第二调试时用print把每一行的heights和max_area打印出来亲眼看到高度数组的变化规律比死记代码管用得多。我有一次调了很久都发现答案是 4最后发现是matrix[0][0]的字符判断写错了排错思路就是靠逐行打印。第三提交代码前一定要测试全1矩形比如 3x3 全是 1和全0的情况。全 0 的情况下heights全是 0栈会一路弹出max_area保持 0这是边界值。全 1 的情况下每一行的最大面积递增最终最大面积是 3x39也要能正确算出来。回到开头那句话0085 最精彩的地方恰恰在从二维到一维的思路跃迁。很多人卡住不是不会单调栈而是没见过把行高度像涓涓细流一样逐层累加这个玩法。一旦你心里有了这个建模再看 0085 就不是困难而是一道中等偏上送分题了。如果觉得自己推演一遍不过瘾建议拿[2,1,5,6,2,3]这个经典用例手写几遍弹栈过程手熟了之后自然就成了肌肉记忆。