刷过hot100的人大概都有这种体会84.柱状图中最大的矩形这题卡住的不是代码量而是“单调栈为什么要这么写”。我第一次看题解时感觉这题像变魔术——明明暴力也能出答案单调栈却在一遍遍历里就把左右边界全算完了。后来把这道题彻底吃透我才意识到它是hot100里一票单调栈题的“题眼”接雨水、最大矩形、每日温度本质上都在复用同一个结算逻辑。这篇文章就围绕84题展开把从暴力到单调栈的完整推导、哨兵写法和实测中的坑一次讲清楚。不管你是还在被单调栈劝退的新手还是想把这道题吃透、准备面试硬仗的选手应该都能从这里拿走点东西。1. 先弄清楚这道题到底在问什么以及为什么暴力解不靠谱1.1 题目回顾与它在hot100里的位置题目本身不长给定n个非负整数表示柱状图中各个柱子的高度每个柱子的宽度为1求该柱状图中能够勾勒出的最大矩形面积。举个例子heights [2, 1, 5, 6, 2, 3]答案是10。这10来自下标2和3两根柱子——高度分别是5和6以5为高、宽度为25×210。注意不是最高的那根6虽然它更高但宽度只有1也不是最矮的那根1高度1能横跨全部6根柱子但面积也只有6。这个例子很刁钻它同时推翻了“最高”和“最宽”两个直觉选项逼着你真正去思考面积怎么组合而不是靠猜。这题在hot100里的邻居也很有意思42接雨水、85最大矩形、739每日温度全是单调栈大家庭的成员。我刷题时有个明显感受很多人能背出“单调栈模板”但一到84题就卡住因为这道题对状态维护的要求比“找下一个更大元素”那种题高一个层次——它不仅要找方向还要在弹出时立刻结算面积。把这题吃透单调栈的“结算时机”这个核心难点就算真的过了。1.2 暴力解到底把算力浪费在了哪里先看最直接的暴力。枚举所有可能的矩形底边区间(i, j)一共有n(n1)/2个区间每个区间的矩形高度等于区间内柱子的最小高度面积就是(j - i 1) * min(heights[i:j1])。实现上固定左端点i向右扩展右端点j同时维护区间最小值可以做到O(n²)。O(n²)是什么概念LeetCode这题的n是10^5级别最坏要跑10^10次运算Python直接超时到天荒地老。就算换C也得跑几十秒面试官看到这个复杂度基本就摇头了。暴力的问题在于区间最小值这个信息在枚举区间时被反复计算和比较但绝大多数区间的结果根本没有机会成为全局最大。比如示例里所有以0号柱为左端、且不包含1号柱的区间矩形高度都被heights[1]1死死压住一旦右端跨过1号柱这个最小值信息又立刻失效。这种“信息随区间伸缩反复失效、反复重算”的问题正是单调栈要解决的——它把每个柱子的有效影响范围用紧凑的顺序结构存起来避免重复扫描。顺着“如何减少无效区间”这个思路往下走就会自然引出另一个完全不同的视角不枚举区间而是枚举高度。2. 从“枚举高度”的视角重构问题单调栈就是顺理成章的事2.1 一个必须接受的关键事实最大矩形的高必然等于某根柱子的高度大多数人看到“柱状图最大矩形”第一反应是找底边区间。但正解的核心洞察是反过来想假设最大矩形的上边在某个高度h它底边覆盖了若干根连续的柱子且这些柱子的高度都大于等于h。那么把矩形向上顶顶到这些柱子里最矮的那根的高度——矩形高度变成那根柱子的高度宽度不变面积反而更大了。这说明一个关键事实任何最大矩形都可以等价成一个“高度恰好等于某根柱子高度、且这根柱子正是矩形底边内最矮一根”的矩形。换句话说最大矩形的解一定落在“以某个柱子为最矮点向左右延伸到第一根比它矮的柱子为止”的矩形集合里。于是我们只需要对每一根柱子i求出它能作为最矮点横向延伸的最远距离算出对应的面积最后取最大值。这个“枚举高度”的思路把问题从n²个区间压缩成了n个柱子每根柱子只需要关心两件事左边第一根比它矮的柱子在哪右边第一根比它矮的柱子又在哪。2.2 左右边界到底怎么定义记柱子i的高度为h。向左看下标l是左边第一根高度小于h的柱子向右看下标r是右边第一根高度小于h的柱子。那么以柱子i为最矮点、高度为h的矩形底边就是(l, r)这个开区间里的所有柱子包括i自己。宽度 r - l - 1面积 h * (r - l - 1)。注意边界条件是“严格小于h”不是“小于等于”。因为高度恰好等于h的柱子不影响矩形高度应该被包含进底边里它能让矩形更宽而不损失高度。比如示例里下标2高度5左边第一根比5矮的是下标1高度1右边第一根比5矮的是下标4高度2所以以5为高的矩形宽度是4 - 1 - 1 2面积正好10。为什么很多题解里写着“小于等于”这是因为实现细节上对相等柱子的处理方式不同。后面讲代码时我会专门说清楚相等柱子用还是触发弹出结果都对但边界处理有区别新手特别容易被这个细节坑到。2.3 单调递增栈怎样才能一遍遍历同时算出左右边界现在问题变成对每根柱子快速找到左右两边最近的矮个子。这是单调栈的经典用武之地。维护一个从栈底到栈顶高度递增的单调栈里面存的是柱子的下标不是高度值。从左到右扫描每个柱子i入栈前先做一件事只要当前柱子的高度小于等于栈顶柱子的高度就把栈顶弹出。注意弹出的这一刻就是被弹出柱子的“结算时刻”它左边第一根比它矮的柱子是谁就是弹出后新的栈顶。因为在它入栈之后所有比它高的柱子都被压在它上面而新的栈顶是唯一还在它左边且比它矮的柱子其他更矮的早就被弹走了。它右边第一根比它矮或等于它的柱子是谁就是当前正在扫描的柱子i。因为如果不存在这样的柱子当前柱子根本不会触发这次弹出。于是每个柱子被弹出时左右边界都齐了面积当场算完。又因为每个柱子只会入栈一次、出栈一次整体时间复杂度O(n)空间复杂度O(n)。用一个生活化的类比来理解“栈里存的都是待结算的人”想象一排人按身高排队新来的人只要看到前方有人比自己高就把那个人拉出来量一次“他能横跨多远”——往左看队列里下一个还站着的人就是他的左墙往右看来的人就是右墙。量完那个人就离开队伍剩下的人继续排队。这样每个人都只被拉出来量一次不需要回头反复比较。3. 完整代码与哨兵写法几个容易被忽视的实现细节3.1 最简Python实现直接上代码先看用触发弹出的版本def largestRectangleArea(heights): # 左右各加一个高度为0的哨兵 heights [0] heights [0] n len(heights) stack [] ans 0 for i in range(n): while stack and heights[i] heights[stack[-1]]: h heights[stack.pop()] left stack[-1] if stack else -1 right i ans max(ans, h * (right - left - 1)) stack.append(i) return ans这段代码连空数组输入也能直接返回0因为加了哨兵后heights至少是[0, 0]遍历完ans还是0。逻辑很短每个柱子入栈前把栈里所有高度不低于它的柱子全部弹出结算。如果用严格小于触发弹出也行def largestRectangleArea(heights): heights [0] heights [0] n len(heights) stack [] ans 0 for i in range(n): while stack and heights[i] heights[stack[-1]]: h heights[stack.pop()] left stack[-1] if stack else -1 right i ans max(ans, h * (right - left - 1)) stack.append(i) return ans两种写法都能通过区别在相等高度的处理策略3.3节细说。3.2 头尾两个哨兵0为什么一个都不能少先说尾部哨兵0。扫描结束后如果栈里还剩柱子没被弹出它们就永远等不到“右边第一根更矮的柱子”来触发结算。最典型的就是严格递增数组比如[1, 2, 3, 4]扫完所有柱子栈里会剩下全部下标一根都弹不出来。尾部补一个高度0扫描到它时必然触发所有剩余柱子被动弹出相当于强制清场结算。没有这个0你只能在for循环结束后再补一个while循环手动结算栈中剩余元素代码丑一倍还容易漏。再说头部哨兵0。它保证栈在任何时刻都不会完全为空——弹出栈顶后取stack[-1]时总有一个垫底元素。从逻辑上看这个0是虚拟的“最左边界”比任何真实柱子的高度都矮所有柱子都不可能跨过它。这样一来“某根柱子左边没有更矮柱子”这种边界情况被自动优雅地处理成0号哨兵的下标不需要额外判断空栈。虽然我在示例代码里还是写了left stack[-1] if stack else -1做保护但加了头哨兵后这行几乎永远不会走else分支。这里有个坑必须提醒如果用触发弹出在遍历到尾部哨兵0时循环可能把头哨兵0也弹出来。为什么因为0 0成立。一旦栈里只剩头哨兵0弹出后stack为空好在while条件第一个判断就是stack and栈空就退出循环不会崩。这个stack and的顺序千万别写反——写成就heights[i] heights[stack[-1]] and stack空栈时直接下标越界这是最容易翻车的细节之一。3.3 相等高度用还是各有道理关键是别混着写面试经常有人问柱子高度相等怎么办比如[3, 3, 3, 3]最大面积应该是4×312。两种写法结果都能到12但过程完全不同。用弹出时第二个3入栈前发现3 栈顶3立刻把第一个3弹出结算。第一个3的右边界算成下标1宽度只有1面积3这不是正确答案但没关系——第二个3入栈、第三个3入栈、第四个3入栈直到尾部哨兵0出现第四个3被弹出时左边界是0号哨兵右边界是5号哨兵算出3×412。也就是说同一高度的柱子先弹出的几个只算出偏小的面积最后一个“代表”被弹出时会补上完整的宽度。用弹出时四个3全部留在栈里等尾部哨兵0出现从右往左逐个弹出。弹出时右边界都是5左边界分别是前一个3的下标最后弹出的那个左边界是0号哨兵同样算出12。我的建议理解阶段用版本因为最贴近“严格小于才是边界”的数学定义写代码阶段用版本栈更紧凑能减少栈里重复高度的下标堆积——只要你记得left那行做空栈保护就行。最怕的就是两种写法混着用比如弹出条件写心里想的却是“严格边界”出了问题非常难查。4. 手跑一遍全流程用样例验证理解和代码4.1 一步步追踪[0, 2, 1, 5, 6, 2, 3, 0]纸上模拟一遍胜过对着屏幕看十遍代码。我用版本手动跑大家跟一遍初始栈[]ans0heights[0, 2, 1, 5, 6, 2, 3, 0]。i0栈空直接入栈栈[0]。i1heights[1]2。20不成立入栈栈[0, 1]。i2heights[2]1。12成立弹出下标1。h2left栈顶0right2面积2*(2-0-1)2ans2。继续10不成立入栈下标2栈[0, 2]。i3heights[3]5。51不成立入栈栈[0, 2, 3]。i4heights[4]6。65不成立入栈栈[0, 2, 3, 4]。i5heights[5]2。26成立弹出下标4。h6left栈顶3right5面积6*(5-3-1)6ans6。继续25成立弹出下标3。h5left栈顶2right5面积5*(5-2-1)10ans10。继续21不成立入栈下标5栈[0, 2, 5]。i6heights[6]3。32不成立入栈栈[0, 2, 5, 6]。i7heights[7]0。03成立弹出下标6。h3left栈顶5right7面积3*(7-5-1)3ans10。02成立弹出下标5。h2left栈顶2right7面积2*(7-2-1)8ans10。01成立弹出下标2。h1left栈顶0right7面积1*(7-0-1)6ans10。00成立弹出下标0。h0left-1right7面积0ans10。入栈下标7。最终ans10。注意一下最大面积10是在下标3高度5被弹出的瞬间算出来的它的左边界是下标2高度1右边界是下标5高度2宽度2高度5。而高度6那根下标4被弹出时只算了6并没有成为答案。这告诉我们最高的柱子不一定产生最大面积因为它两边可能立刻就有矮柱子把它限制住。单调栈的结算顺序本质上是“每个柱子只有在找到右边界时才有资格结算”所以结算顺序和柱子原始下标的先后关系不大。4.2 写个小对拍脚本把代码跑在随机数组上面试准备阶段我强烈建议写一个对拍工具来验证单调栈实现和暴力解是否一致。思路很简单随机生成大量小规模数组用单调栈函数算答案同时用暴力两层循环算答案不一致就打印出来。import random def brute(heights): n len(heights) ans 0 for i in range(n): h heights[i] for j in range(i, n): h min(h, heights[j]) ans max(ans, h * (j - i 1)) return ans def monotonic(heights): a [0] heights [0] stack [] ans 0 for i, x in enumerate(a): while stack and a[stack[-1]] x: h a[stack.pop()] left stack[-1] if stack else -1 ans max(ans, h * (i - left - 1)) stack.append(i) return ans for _ in range(10000): heights [random.randint(0, 20) for _ in range(random.randint(1, 50))] b, m brute(heights), monotonic(heights) if b ! m: print(heights, b, m) break else: print(all ok)这段代码我实测过跑一万组随机数据两种结果始终一致。对拍的价值在于它把“我以为我理解了”变成“我验证了我理解了”。刷算法题最怕的是背了模板能过题换一个变形题就不会了对拍能强迫你从原理层面修正每一处细节错误。对拍用的monotonic函数弹出条件是a[stack[-1]] x也就是严格大于版本。你把弹出条件改成再跑结果同样一致可以自己动手试试。5. 从84题发散同套路题组和面试追问5.1 85最大矩形二维数组先压缩再调84LeetCode 85题“最大矩形”是84题最直接的应用。输入是一个01矩阵要求找出全部由1组成的最大矩形面积。做法非常固定按行从上到下扫描维护一个高度数组heightsheights[j]表示从当前行向上连续1的个数。如果当前行第j列是1heights[j]加1如果是0heights[j]清零。每处理完一行就对当前heights数组调用一次84题的求解函数更新全局最大面积。为什么可以这样压缩因为矩形在二维矩阵里至少要有一条底边落在某一行上。我们把每一行当作柱状图的底矩形的高度就是它能向上连续延伸的1的个数。这样二维问题被拆成一维跑m行每行一次84题总复杂度O(m*n)。这是很典型的“降维打击”面试考85题时直接把84的函数拿出来复用就行面试官通常会很满意。5.2 42接雨水同一个栈方向反了一下很多人在84和42之间反复横跳我做个对比。42题“接雨水”维护的是单调递减栈遍历时如果当前柱子比栈顶高说明栈顶柱子两侧都出现了更高的墙中间形成凹槽可以结算水量。而84题维护的是单调递增栈当前柱子比栈顶矮时栈顶柱子的右边界出现结算的是矩形面积。一个找“凹下去能装水的地方”一个找“凸起来的覆盖范围”刚好互补。另一个细节区别接雨水遇到相等高度时不能随便弹出否则会把平顶的凹槽错误结算84题遇到相等高度两种写法都能通过前面已经详细解释过。如果把84彻底搞懂再去看42你会发现两题的“结算时机”是同一个套路——某个柱子在被弹出的一瞬间它的左边界和右边界同时确定之后是算面积、算水量还是算距离只是题面不同。5.3 739每日温度与496下一个更大元素同一个抽象模板739题求的是每个温度右边第一个更高温度的距离维护单调递增栈遇到更高温度时弹出栈顶用当前下标减栈顶下标记录答案。496题求每个元素右边第一个更大的值套路几乎一致。这三道题加上84和42基本覆盖了单调栈面试的全部基础题型。它们的公共模板可以抽象成一句话维护一个栈让栈内元素保持某种单调性当即将入栈的元素破坏了单调性时不断弹出栈顶元素并在弹出的瞬间根据左右信息结算答案。区别只在于栈里存下标还是存值单调递增还是单调递减弹出时计算的是面积、水量、距离还是下一个更大元素是否要处理循环数组比如503题遍历两倍长度、下标取模即可。这个抽象一旦建立遇到新的单调栈题你的第一反应就不会是“背模板”而是先问自己破坏单调性的瞬间那个被弹出的元素知道了什么信息这个信息怎么变成答案5.4 几个面试高频追问和我的应对思路面试官在84题之后经常追加问题我整理一下自己的思路为什么不能用双指针左右夹逼矩形面积取决于区间最小值而区间最小值随左右指针移动不呈现单调性你没法判断该动左边还是动右边。能用双指针的题比如11题“盛最多水的容器”面积只取决于两端高度且有明确的单调决策情况完全不同。全零数组或空数组怎么办哨兵机制天然处理成ans0不需要特判。能不能用分治或线段树可以O(n log n)级别但面试场合O(n)的单调栈是最优解分治更多是作为扩展讨论出现。高度会不会有极大值题目保证非负整数但实现时要注意面积中间结果可能超过32位整数。Python没有溢出问题C或Java建议用long。这些追问的大方向只有一个确认你是否真的理解了“结算时机”和“边界定义”而不是把代码背下来。我准备这道题时要求自己做到能脱离代码、徒手在纸上画哨兵数组的完整结算过程每次被追问边界条件就在心里跑一遍基本都能应付。最后分享一个我个人实测有效的习惯学84题时别急着一次写对先故意写一个不带哨兵的版本用[1, 2, 3, 4]这种递增数组跑一遍亲眼看到栈里剩下柱子没结算、答案错误然后再补上哨兵。这样你对两个0的作用会有肌肉级别的记忆下次再写单调栈题哨兵几乎是自动出现在脑海里的。这个习惯帮我躲过了很多次面试现场的边界翻车希望对你也同样有用。