很多刷题的人把 LeetCode 84 题《柱状图中最大的矩形》当作“单调栈劝退题”刷完一遍感觉会了过两周再碰又想不起来。这道题我在不同阶段写过好几种版本从最开始的暴力枚举到后来用哨兵写单调栈踩过的坑也不少。它名义上是困难题但只要把“为什么能用栈”这件事想明白代码其实就十几行而且这套思路在“接雨水”“每日温度”“最大子矩阵”里全都能复用。这篇文章我不打算只贴一段能过的代码。我会按“暴力思路 - 单调栈原理 - 代码落地 - 常见坑点 - 面试扩展”的顺序把每一步为什么要这么做讲清楚。你如果是第一次接触这道题按这个顺序读下来基本能独立写出来如果是准备面试可以直接跳到第五、六部分那些才是真正拉开差距的地方。1. 先从暴力解法说起搞清楚题目到底在算什么1.1 题面拆解其实就是选矩形题目给了你一个数组heights每个元素代表柱子的高度柱子的宽度固定为 1。要求在这个直方图里找一个矩形这个矩形的底边必须平行于 x 轴左边和右边都必须贴着某根柱子的边缘向上能盖住的部分不能悬空也就是说矩形的高度取决于它覆盖的那一段区间里最矮的那根柱子。换句话说给定区间[left, right]这个区间能形成的最大矩形面积是面积 (right - left 1) * min(heights[left..right])我们的目标就是遍历所有可能的[left, right]找这个面积的最大值。这里最直白的解法就是双重循环枚举左右边界区间内找最小值整体复杂度 O(n^3)你甚至不用写代码就知道肯定过不了。稍微优化一下固定左边界向右扩展右边界时同步维护当前区间的最小值这样能把找最小值的 O(n) 省掉变成 O(n^2)。看个具体例子heights [2, 1, 5, 6, 2, 3]。如果固定左边界为下标 2高度 5右边界往右扩区间 [2,2]最小值 5面积 5区间 [2,3]最小值 5面积 10区间 [2,4]最小值 2面积 6区间 [2,5]最小值 2面积 8这个过程中最大面积是 10。但你要知道最终答案其实是 10对应区间 [2,3]矩形高度 5宽度 2。再看看所有区间里的最大值你会发现 10 就是答案。暴力做法的正确性不用怀疑问题只在效率。当n 10^5级别时O(n^2) 在极限数据下会超时所以必须把复杂度压到 O(n log n) 甚至 O(n)。1.2 换个枚举视角以每一根柱子为矩形高度暴力枚举区间的做法虽然直观但它没有利用“每一根柱子高度已知”这个信息。实际上我们可以换个思路假设最终答案的矩形高度是 h那么这个矩形在直方图里对应的底边一定是横跨了一段连续区域这段区域里所有柱子的高度都大于等于 h同时这段区域的左右两边要么是边界要么存在一根高度小于 h 的柱子挡住。于是就有了另一种枚举方式对每一根柱子i假设它就是矩形的最高限制也就是矩形高度恰好等于heights[i]。为了让它能尽可能宽我们需要找到它左边第一根高度小于heights[i]的柱子以及右边第一根高度小于heights[i]的柱子。这两根柱子之间的所有柱子高度都不低于heights[i]所以可以用这个高度填满整个区间。这个思路的正确性在于任何一个最优矩形它的高度一定等于某个柱子的高度。如果矩形高度不严格等于某根柱子的高度那么它可以继续向上扩展直到被某根更矮的柱子挡住这个时候矩形高度就等于那根“挡住的柱子”的高度。所以枚举所有柱子作为“最矮限制”一定能覆盖到最优解。现在问题变成怎么快速求出每根柱子左边第一个更矮的位置和右边第一个更矮的位置。这就是单调栈登场的时刻。2. 单调栈的原理它到底在维护什么信息2.1 用一个生活类比理解“左边第一个更矮”想象你在排队买奶茶每个人的头顶标着自己的高度。你想知道每个人左边第一个比自己矮的人是谁。最笨的办法当然是每个人往左看逐个比较总体复杂度 O(n^2)。如果换一种玩法从左往右扫这个队伍同时手里维护一个“候选名单”。每当新来一个人就把名单里所有比他高或和他一样高的人删掉因为这些人对于后面的人来说已经完全没用了——后面的人找“左边第一个比我矮的”而被删掉的这些人要么太高要么和新来的一样高新来的人位置更靠右更有资格作为“第一个更矮/不高”的候选。处理完之后名单里剩下的最后一个人就是新来的人左边第一个比自己矮这里细节上要看等号怎么处理后面会说的人。然后把新来的人放进名单末尾。你可以亲手试一下heights [2,1,5,6,2,3]按这个规则走一遍你会发现过程中名单永远是一个单调递增的序列。这就是“单调栈”这个名字的由来。我们用一个栈来维护这个名单栈底的元素最靠左栈顶元素最靠右从栈底到栈顶柱子高度严格递增。2.2 计算面积的关键右边界触发“结算”知道了每根柱子左边第一个更矮的位置leftLess[i]右边第一个更矮的位置rightLess[i]面积公式就是area heights[i] * (rightLess[i] - leftLess[i] - 1)但这里有个更妙的点不需要分别求出leftLess和rightLess两个数组再算面积。单调栈在弹栈的那一刻就是结算那根柱子面积的最佳时机。为什么因为栈里维护的是递增序列当新来的柱子高度比栈顶矮时说明栈顶那根柱子的“右边第一个更矮”出现了。而这个柱子左边的更矮位置就是它弹出后在栈里变成新的栈顶的那根柱子。两边信息都齐了直接算。这就像你在玩“俄罗斯方块”每根柱子入栈相当于方块落下当它被更高的方块挡住时先存着一旦遇到更矮的方块它能向左扩展的宽度就到头了这时候结算面积。2.3 面积公式的左右边界推导假设当前栈从左到右是[bottom ... p, x, ... top]现在新来的柱子i高度小于heights[top]我们要弹出top以它作为矩形高度。设弹出的柱子下标为cur。左边界弹出后新的栈顶p它就是cur左边第一个高度小于等于或严格小于看等号策略heights[cur]的柱子。因此左边界位置就是p区间左端点是p 1。右边界当前这个逼着cur弹出的柱子i就是cur右边第一个高度严格小于heights[cur]的柱子。因此右边界位置是i区间右端点是i - 1。于是宽度为width (i - 1) - (p 1) 1 i - p - 1如果栈里没有元素了说明cur左侧没有更矮的柱子那左边界就是 -1想象一个虚拟的负一位置高度为负无穷宽度公式就变成i - (-1) - 1 i。这个公式是整道题最核心的地方。网上很多代码你看着像背下来的其实就是把左右边界的位置套进宽度公式而已。2.4 等号处理严格小于还是小于等于一个最常见的细节问题是弹出栈顶的条件是heights[i] heights[st.top()]还是heights[i] heights[st.top()]。用严格小于也就是遇到相等时不弹出的写法会导致相同高度的柱子会重复入栈但算面积时依然正确只是栈里会出现多个高度相同的下标结算时可能多算几次浪费一点时间复杂度仍然是 O(n)。用小于等于遇到相等时弹出的写法相同高度的柱子会在第一次遇到更矮柱子时被统一结算逻辑更干净也不会漏解。我个人推荐用即弹出条件写成heights[i] heights[st.top()]。这是因为用严格小于时两个相同高度的柱子之间会被当作“左边界”导致宽度计算出现偏差吗并不会。但用的好处是每个高度的柱子最多入栈一次出栈一次语义更统一避免你在调试时遇到“为什么这个高度算了两次”的困惑。不管用哪种你心里必须清楚一点对于高度相同的柱子它们对应的矩形面积是相同的。使用后最左边那根相同高度的柱子会在结算时把宽度扩展到包含所有右边相同高度的柱子这样面积不会少算。3. 完整代码落地哨兵写法确实是最省心的3.1 从无哨兵版本开始理解等价边界条件先看一个不添加哨兵的版本这样你能清楚每一步在干什么def largestRectangleArea(heights): stack [] max_area 0 n len(heights) for i in range(n): while stack and heights[i] heights[stack[-1]]: cur stack.pop() left stack[-1] if stack else -1 width i - left - 1 max_area max(max_area, heights[cur] * width) stack.append(i) while stack: cur stack.pop() left stack[-1] if stack else -1 width n - left - 1 max_area max(max_area, heights[cur] * width) return max_area这个版本的问题在于循环结束后栈里可能还剩一堆下标这些柱子右边没有更矮的柱子了右边界就是数组长度n。所以需要单独写一个while stack的收尾循环。很多刚开始写的人容易漏掉这个收尾结果答案偏小。这里right用n而不是n-1因为宽度公式是right - left - 1我们把右边界视为“第一个更矮位置的索引”当没有更矮时虚拟位置就是n。3.2 哨兵版本左右各加一个 0代码更短如果我们在heights最前面和最后面各插入一个高度为 0 的柱子就能让每个元素都能在循环过程中被弹出省去收尾循环。同时左侧的 0 还能保证栈不为空省去每次判断stack[-1] if stack else -1。def largestRectangleArea(heights): # 尾部加0保证所有柱子最后都能被弹出 # 头部加0保证栈永远不为空左边界好处理 heights [0] heights [0] stack [] max_area 0 for i in range(len(heights)): while stack and heights[i] heights[stack[-1]]: cur stack.pop() left stack[-1] width i - left - 1 max_area max(max_area, heights[cur] * width) stack.append(i) return max_area注意这里弹出条件用了严格小于。为什么加了哨兵还要配而不是因为如果遇到相等也弹出左侧哨兵 0 也可能在某种极端情况下被弹掉不会因为哨兵是 0当i指向最右侧的 0 时heights[i] 0如果用会把前面所有高度为 0 的哨兵弹出。但正因为加入了左哨兵即便用也不会出错只是栈底始终有一个 0 保证非空。不过为了保证语义清晰我用。这样遇到相等的柱子时不急着结算等到更矮的柱子出现时栈里连续相同高度的柱子会依次弹出宽度计算依然正确。3.3 时间复杂度分析为什么每个元素只进出栈一次很多人担心内层while循环会不会导致整体 O(n^2)。关键点在于每个下标在入栈后最多被弹出一次。外层循环每轮只会把一个下标压入栈而内层while每次弹出一个下标所有下标弹出的总次数不超过n次。因此总操作次数是 O(n) 的均摊复杂度。这个均摊逻辑可以这样理解你在食堂排队打饭每个人最多被“挤出队伍”一次后面来的人不可能把已经走掉的人再挤一遍。所以无论嵌套循环长什么样总出栈次数有上限。3.4 用测试用例验证代码行为拿题目示例heights [2, 1, 5, 6, 2, 3]手动推一遍加入哨兵后数组为[0, 2, 1, 5, 6, 2, 3, 0]循环到 i1高度2栈空入栈栈[0,1]i2高度1比栈顶2矮弹出cur1left0width1面积2*12入栈2栈[0,2]i3高度5入栈栈[0,2,3]i4高度6入栈栈[0,2,3,4]i5高度2弹出cur4高度6left3width1面积6再弹出cur3高度5left2width2面积10max_area更新为10入栈5栈[0,2,5]i6高度3入栈栈[0,2,5,6]i7高度0弹出cur6高度3left5width1面积3弹出cur5高度2left2width4面积8弹出cur2高度1left0width6面积6最后 max_area 是 10正确。你会发现每次弹出的时机就是那根柱子作为“最低高度”所能覆盖的区间刚好结束的时候很有节奏感。4. 常见坑点与排查实录4.1 忘记处理栈内剩余元素这是新手最容易犯的错误。没有哨兵时循环结束后栈里还留着一些右侧没有更矮柱子的下标。如果直接返回max_area会漏掉以这些柱子为高度的矩形。排查方法如果测试用例里答案是单调递增数组比如heights [1, 2, 3, 4, 5]你会发现输出不对。建议你在写无哨兵版本时先用这个用例走一遍代码感受一下收尾循环的作用。4.2 等号处理引发的面积偏差如果弹出条件写成heights[i] heights[stack[-1]]而你没有意识到这种写法下宽度计算对相等高度柱子要特别小心容易出现面积偏小或偏大的错觉。举个极端例子heights [2, 2, 2]正确答案是 6。如果用并且忽略收尾结算计算过程会有点绕如果用第一个 2 会在遇到第二个 2 时被弹出宽度为 1面积 2第二个 2 遇到第三个 2 时弹出面积 2第三个 2 遇到末尾哨兵 0 时弹出此时栈内前面的柱子都弹光了左边界是哨兵 0宽度为 3面积 6最终答案正确。实际上两种等号策略都能算出正确答案但“为什么正确”的理解深度不同。面试时如果被问到这个细节能说清楚让相同高度柱子在最后一次结算时把宽度扩展到最大是加分项。4.3 数组为空或只有一个元素加了哨兵后空数组会变成[0, 0]循环过程中不会进入while结果返回 0正常。单元素数组[5]变成[0, 5, 0]遍历到 i1 时入栈i2 弹出宽度2 - 0 - 1 1面积 5正常。如果你写的是无哨兵版本记得对空数组做特判。忽略空数组会导致n 0for 循环不执行while 也不执行返回 0其实也不会出错。真正容易出错的场景是heights [0]这时候栈里会压入一个高度为 0 的下标最终弹出的面积也是 0没问题。4.4 用哨兵时忘记左哨兵也是数据的一部分加入哨兵后数组长度变了循环范围要跟着变。很多人在写for i in range(len(heights))时没问题但手动推导时会搞混原始下标和带哨兵下标。建议调试时打印i、stack、max_area每一步对应关系就清楚了。4.5 面积初始值设置最大值初始设为 0 就行因为矩形高度和宽度都是非负的。有的题解会初始化为负无穷没必要。不过如果你复用模板去做一些矩形面积可能为负值的变体题那就另当别论。5. 除了单调栈还有哪些解法值得了解5.1 分治法思路区间[l, r]的最大矩形面积要么完全在左半边要么完全在右半边要么跨过中点。跨过中点的部分需要从中间向两边扩展同时维护当前最小高度逐步计算面积。复杂度是 O(n log n)最坏情况下数组单调会退化成 O(n^2)。如果对分治不熟可以作为扩展阅读不建议作为面试首选方案。5.2 枚举高度 前缀信息先确定某个高度然后找这个高度能延伸的最长宽度。等价于对每个柱子找左右第一个更矮的位置这恰好是单调栈做的事。所以这个思路本质上就是单调栈的另一种描述方式。面试时如果你先从“枚举高度”角度切入再引导出单调栈会显得思路非常自然。5.3 几种解法对比我整理了一个简表方便你复习时快速回忆解法时间复杂度空间复杂度优点缺点枚举区间暴力O(n^2) 或 O(n^3)O(1)正确性直观大数据超时分治O(n log n)O(log n)思路清晰最坏退化实现复杂单调栈无哨兵O(n)O(n)容易理解边界需要收尾循环单调栈哨兵O(n)O(n)代码简洁无收尾需要理解哨兵作用面试推荐写哨兵版本因为代码短边界少不容易写错。6. 面试现场这道题背后的考察点与扩展延伸6.1 面试官常见的追问方式你写完单调栈后面试官大概率会追问这几个问题第一个是“为什么用单调栈而不是单调队列”。你要能回答这题需要的是左侧和右侧两边最近的更矮位置单调栈天然能维护这种“上一个更小元素”的信息单调队列通常用于维护滑动窗口内的极值场景不同。第二个是“时间复杂度为什么是 O(n)”。要答到均摊分析每个元素入栈一次、出栈最多一次所以整体线性。第三个是“如果柱子高度有负数怎么办”。这题数组元素是非负整数但如果改成允许负数单调栈解法就不太适用因为“最小高度为负”会破坏矩形的非负性假设。工程上遇到类似问题要从头分析约束。第四个是“能不能用 O(1) 额外空间”。可以借助类似“接雨水”的双指针思路做一遍但比较绕复杂度仍可控。面试一般不会要求到这个程度但如果能讲出来会很加分。6.2 这道题的经典变形最大矩形问题的二维版本是 LeetCode 85《最大矩形》给定一个 01 矩阵找到只包含 1 的最大矩形。解法是把每一行看成柱状图高度数组逐行累加然后对每一行调用本题的函数。这也是 84 题最重要的延伸应用。其他相关的变形题还有接雨水同样是单调栈但算的是凹槽面积结算逻辑相反。每日温度求右边第一个更高温度的距离单调栈模板几乎一样。子数组最小值的和、最大宽度坡等都用到了“找左右边界”的单调栈思想。6.3 我的个人体会这道题我前前后后写过不下十遍每次重写都有新的理解。最初我只知道“用单调栈遇到矮的就弹”后来才真正想清楚为什么要用栈、弹栈时宽度公式怎么来的、等号要怎么处理。这提醒我一个很重要的道理算法模板可以背但如果不理解背后的“为什么”一到变形题就露馅。如果你正在准备面试我建议你在纸上手动推演一遍带哨兵的代码把每一步的栈变化和面积更新写出来推完一遍基本就忘不掉了。面试的时候如果紧张也可以先跟面试官说“我打算用单调栈维护一个递增序列在弹栈时结算面积”这句话一出口思路就清晰了大半。另外一个实用的小技巧把heights [0] heights [0]的开头写在函数最前面然后心安理得地在循环里不再判断栈是否为空。这行代码几乎就是这道题的灵魂理解它为什么存在比记住整个模板重要得多。