柱状图最大矩形这类题目在算法面试里算是一眼觉得不难一上手全是细节的典型。很多人第一反应是暴力枚举区间写起来确实几分钟就能跑通样例但数据量一上去就原形毕露。这篇我会从暴力演化到单调栈把边界处理和等高柱子的坑一次讲透并附上可以直接照抄的代码和调试方法。先说结论这道题有至少五种解法——暴力枚举区间、枚举柱子往两边扩展、前缀最小值优化、分治以及最优的单调栈。单调栈的思路不是背模板而是理解一个关键点每个柱子的最大辐射面积只有遇到右边第一个比它矮的柱子时才能真正确定下来。抓住这条主线代码写不写得对就只差细节层面了。1. 题目本质与暴力解法的复杂度陷阱1.1 题面拆解到底在求什么给定n个非负整数表示柱状图中每根柱子的高度每个柱子宽度是 1。要求在这些柱子能围成的所有矩形里找面积最大的那个。注意几个容易忽视的限定高度是非负整数所以存在大量高度为 0 的柱子。宽度恒为 1所以一个矩形的宽度 连续柱子的数量。矩形不能悬空它必须坐落在连续的一组柱子之上且矩形高度不能超过这组柱子里最矮的那根。换句话说任意一个合法矩形都对应一个连续区间[left, right]矩形高度 min(height[left..right])。题目就变成了在所有连续区间里最大化区间长度 × 区间最小值。1.2 暴力枚举的所有写法以及它们为什么慢写法一穷举所有左右边界两层循环枚举左边界i和右边界j然后内层再算区间最小值。三层循环嵌套复杂度O(n³)。这个写法连 LeetCode 的样例都得看运气才能过基本不配出现在考场答案里后续我们不会再提它。写法二固定左边界向右维护最小值左边界i定住右边界j向右移动时实时用一个变量记录当前区间最小值。这样少了一层循环复杂度降到O(n²)def largestRectangleArea_bf(height): n len(height) ans 0 for i in range(n): min_h height[i] for j in range(i, n): min_h min(min_h, height[j]) ans max(ans, (j - i 1) * min_h) return ans这个版本的思路是枚举左边界向右不断扩展实时收紧最低高度。因为每次右移右边界宽度j - i 1只会变大高度min_h只会变小两者是跷跷板关系所以需要随时更新答案。写法三每根柱子作为最低点向两边扩展对每一根柱子i假设它就是要找的那个矩形的最低点。然后从i向左走找到第一个高度严格比heights[i]矮的位置再向右走找到第一个严格更矮的位置。这样以heights[i]为高的最大矩形区间就确定为(leftBound 1, rightBound - 1)。面积自然能算出来。这个思路的复杂度最坏也是O(n²)——比如所有柱子高度都相等每根柱子向左向右都要扫到边界。def largestRectangleArea_expand(height): n len(height) ans 0 for i in range(n): l i while l - 1 0 and height[l - 1] height[i]: l - 1 r i while r 1 n and height[r 1] height[i]: r 1 ans max(ans, (r - l 1) * height[i]) return ans写到这里读者应该能感受到一个矛盾枚举每根柱子作为最低点的思路方向是对的——因为任何合法最大矩形的高度必然等于区间内某根柱子的高度否则还可以更高。问题只在于向两边扩展这一步太费时。我们真正需要的是一次性高效求出每根柱子的左右边界这就是单调栈登场的契机。2. 为什么面积要等到遇到更矮的柱子时才算得出来2.1 核心观察右边界在遍历中才逐步揭晓假设我们在从左往右扫描柱子同时脑子里在追踪某个高度为h的柱子。请想一个问题如果右边的柱子一根比一根高你能确定这根高度为h的柱子往右最远能辐射到哪里吗不能。因为下一根更高的柱子完全可以继续撑住高度h的矩形宽度还能继续增加。反过来只要遇到了第一根高度小于h的柱子那么以h为高、从当前柱子向左延伸直到被左边某个更矮的柱子挡住所能组成的最大矩形就彻底确定了。因为再往右哪怕一格高度都得小于h矩形被迫变矮。所以面积的计算时机不是每根柱子入栈时而是当它从栈中被弹出时。2.2 用排队场景理解单调栈的进出你把每一根柱子想象成排队买票的人每个人手里举着一个数字高度。售票窗口有个规则队伍里所有人的身高必须从左到右严格递增新来的人如果身高比队尾的人高直接排到队尾如果比队尾矮就让队尾的人出队结算工资结算完他就离开队伍不再参与后续直到新来的人能插入队伍。这个结算动作对应程序里的 弹出栈顶元素计算以它为最低点、当前遍历到的柱子作为右边界时的最大面积。为什么结算以新来矮个子为右边界因为对那个被弹出栈的高个子来说矮个子就是他右边第一个比他矮的柱子。他职业生涯的右边终点已经到了没有继续扩张的可能只能结算。整个过程保证栈内元素高度单调递增所以叫单调栈。2.3 对比接雨水的单调栈理解方向差异很多读者在接雨水那道题也见过单调栈但那里是单调递减栈栈底到栈顶高度递减因为接雨水要找两边高中间低的凹槽而本题是单调递增栈栈底到栈顶高度递增因为我们要不断寻找左边矮、右边也矮的凸顶。这个方向千万不要背反。判断依据很简单你结算的是谁接雨水结算的是被夹住的低谷而本题结算的是凸起的高峰。高峰自然对应递增结构低谷对应递减结构。3. 单调栈代码拆解下标、宽度公式与等高柱子的处理3.1 为什么栈里存下标而不是直接存高度面积计算依赖三要素高度、左边界、右边界。右边界就是当前扫描到的下标i。高度可以直接通过heights[下标]拿到。左边界则藏在弹出后的新栈顶里。如果栈里只存高度我们无法知道左边界在哪。下标是唯一能让三要素对齐的信息。这是单调栈题目里最常见的一个共识能存下标就存下标需要高度时再查数组。3.2 弹出时的宽度公式推导假设栈内元素的下标栈底到栈顶是递增的高度也是递增的。现在扫描到下标i发现heights[i] heights[stack[-1]]于是不断弹出栈顶。设弹出的下标为top它对应的高度是h heights[top]。右边界显然是当前下标i。因为i是第一个能让栈顶弹出的位置。左边界弹出top之后新的栈顶stack[-1]表示左边第一个高度小于等于h的柱子的下标这个小于等于是等高策略的产物下文马上说。那么宽度就是i - stack[-1] - 1。面积 h * (i - stack[-1] - 1)。为什么是i - stack[-1] - 1而不是i - top因为top到i之间的那些柱子早就在之前的过程中被弹出去结算了。它们的下标不在栈里但它们的高度都大于等于h这些柱子全都能成为高为h的矩形的底。所以左边界必须用新栈顶来定位而不是用top——这恰恰是单调栈的精髓。下面的极端例子能说明问题高度数组[2, 1, 5, 6, 2, 3]处理到下标4高度 2时栈里情况很微妙。假设我们模拟一下细节用代码实现但宽度逻辑可以预先体会。3.3 等高柱子用 还是 弹出这是无数人写错的一个细节值得单独拎出来。假设高度数组是[2, 2, 2]。如果弹出条件是heights[i] 栈顶高度即等高时不弹出三根柱子会怎样下标 0 入栈。下标 1 高度也是 2不小于栈顶所以也入栈。下标 2 同样入栈。最后清空栈时下标 2 弹出计算宽度以它自己为基准向左扩展假设栈里还有 0 和 1宽度可以算出为2 - (-1) - 1 2面积2 * 2 4。下标 1 弹出时栈顶是 0宽度2 - 0 - 1 1 这就错了因为下标 1 到 2 之间明明还有一根柱子它完全能撑起高度 2 的矩形宽度应该至少是 2 甚至 3。问题出在哪等高柱子之间互为右边界但如果你迟迟不把左边那个等高的柱子弹出去它在后面计算时左边边界会正确、右边边界却被新的等高柱子遮挡了真实延伸范围。看似无伤大雅但面积会算小。使用heights[i] heights[stack[-1]]作为弹出条件时等高柱子会被立刻弹出。弹下标 1 时面积按右边界i 2左边界取下标 0宽度 2 - 0 - 1 1依然只得到 1。这又错了别急正确答案是面积最大的2 × 3 6是在处理到数组末尾的哨兵时算出来的。等到最后一根下标 2 弹出时左边界是-1哨兵右边界是哨兵下标 3宽度 3 - (-1) - 1 3面积6。也就是说等高的三根柱子最终结算的是最右边那一根它把左边所有等高柱子的面积算全了。如果你的弹出条件是每一根等高柱子都会在遇到下一根等高柱子时被结算但那些结算的宽度会偏小。真正兜底的是最后一根等高柱子 右哨兵那次结算。所以必须配合下一节的哨兵技巧才能正确收尾。另一种策略是弹出条件用严格小于才弹即等高不弹。这时候假设数组[2, 2, 2]三根柱子全部入栈最后清栈时弹出下标 2此时栈中有 0、1。左边界 下标 1宽度 3 - 1 - 1 1这依然是 1不对。等等——这里就需要我们额外处理。等高不弹的话后面的等高柱子的右边界永远无法变成前面柱子的左边界这会导致宽度计算范围缩小。所以标准答案里几乎清一色使用弹出条件 左右哨兵。的本质是让等高柱子尽早结算把连续等高段的面积留给最右侧那根在遇到最终矮子或哨兵时一次算完。实践中最稳妥的记忆方式弹出条件写while stack and heights[i] heights[stack[-1]]:配套左右哨兵正确性有保证。4. 两种实用写法预处理左右边界 与 O(n) 单次遍历 哨兵4.1 预处理法先求每个柱子的左右边界再算面积这是最直白的单调栈应用。一次从左往右扫描用单调递增栈求每个位置的left[i]左边第一个高度小于自己的柱子下标再一次从右往左扫描求right[i]右边第一个高度小于自己的柱子下标。def largestRectangleArea_pre(height): n len(height) left [-1] * n stack [] for i in range(n): while stack and height[stack[-1]] height[i]: stack.pop() left[i] stack[-1] if stack else -1 stack.append(i) right [n] * n stack.clear() for i in range(n - 1, -1, -1): while stack and height[stack[-1]] height[i]: stack.pop() right[i] stack[-1] if stack else n stack.append(i) ans 0 for i in range(n): ans max(ans, height[i] * (right[i] - left[i] - 1)) return ans上面这段代码把左开右开区间写得很明白left[i]是左边第一个小于height[i]的柱子下标right[i]是右边第一个小于height[i]]的下标。面积宽度 right[i] - left[i] - 1。这段代码的正确性一目了然适合当作理解用代码。缺点是代码稍长且两轮扫描 一轮计算 3 个循环虽然是O(n)但常数略大。4.2 哨兵优化一次遍历搞定一切我们其实不需要真的预先算出左右边界。模拟一遍从左往右遍历遇到heights[i]小于栈顶时不断弹出栈顶并结算。弹出的top其右边界就是当前i左边界就是弹出后的新栈顶。遍历结束栈里可能还有剩余元素它们的右边界全是n数组最右的哨兵位置需要再写一段 while 循环。这段收尾代码很容易漏。更优雅的方案是数组头部和尾部各插入一个高度为 0 的哨兵左哨兵height 0保证栈永远不会彻底空宽度计算时左边界始终有值。右哨兵height 0会在遍历的最后一位强制弹出栈内所有剩余柱子省掉收尾循环。源码如下def largestRectangleArea(height): # 左右各加一个高度为0的哨兵 heights [0] height [0] n len(heights) stack [] ans 0 for i in range(n): while stack and heights[i] heights[stack[-1]]: top stack.pop() # 左边界 弹出后新栈顶栈里还有左哨兵兜底 width i - stack[-1] - 1 ans max(ans, heights[top] * width) stack.append(i) return ans注意第 7 行我写的是而不是。你可能要问了前面不是说要用吗这里有个精妙的差异加入哨兵后也能正确处理等高情况。原因是等高的柱子不会立即互相弹出它们会全部留在栈中。当遇到真正的矮柱子或右哨兵时这些等高柱子从右往左依次弹出。每次弹出时左边界恰好是左侧等高柱子但高度相同宽度却不重叠——最终最左侧那根等高柱子弹出时它的左边界是更矮的柱子右边界是触发弹出的下标宽度把整个等高段全部覆盖了。所以总和不会漏。但话说回来配合哨兵也完全正确而且对新手来说逻辑更连贯等高立即结算。两种写法在这个框架下都能过你喜欢哪种用哪种。我自己更习惯因为代码里少写一个等号而且出栈次数更少一些常数上略有优势。面试时请坚持用你练熟的那一种临场换写法容易翻车。4.3 哨兵下标与宽度公式的边界推演很多人第一次写哨兵版本时会被width i - stack[-1] - 1里的stack[-1]弄晕。我们推演一个最小例子height [2]。构造heights [0, 2, 0]。i0高度 0栈空0 入栈。此时stack [0]。i1高度 2while条件0 2不成立。2 入栈。stack [0, 1]。i2高度 0while条件0 2成立弹出top 1。此时stack[-1] 0宽度 2 - 0 - 1 1面积 2 × 1 2。正确。接着while条件0 0不成立。下标 2 入栈结束。宽度公式里的stack[-1]是弹出后的栈顶这个顺序在代码里体现为先pop()拿到top再访问stack[-1]。如果你先取了stack[-1]再 pop或者 pop 之后又用top当左边界宽度就错了。4.4 复杂度分析每个下标最多入栈一次、出栈一次。每次出栈执行常数次运算。总时间复杂度O(n)空间复杂度O(n)栈存下标。排序算法做不到O(n)的很多场景这里因为维护了局部的单调性把每个元素只结算一次所以能做到线性。这也是面试时一定要点明的时间复杂度证明——只说用单调栈而不说清为什么是O(n)面试官往往还会追问一轮。5. 从这道题延伸出去的三个高频变体5.1 变体一LeetCode 85最大全1矩形给定一个只含 0 和 1 的二维矩阵求全是 1 的最大矩形面积。解法是把矩阵按行压扁成柱状图对每一行heights[j]表示从当前行往上连续 1 的个数遇 0 则清零。然后对每一行调用本题的单调栈函数更新全局最大值。时间复杂度O(m × n)。这个变体几乎就是为本题量身定做的应用题。做过本题再去写 85 题通常只需要半小时不到。5.2 变体二接雨水LeetCode 42同样用单调栈但栈是单调递减的。遇到凹槽时结算水量弹出栈顶作为底取左右两侧较矮的一侧作为水位水量 (min(左高, 右高) - 底高) × 宽度。对比两题你会发现单调栈的结算时机完全不同接雨水结算的是被矮的栈顶卡住的区间而本题结算的是被高个撑起来的高峰区间。做题时先把要结算的对象想清楚单调栈的增减方向就不会搞反。5.3 变体三每日温度LeetCode 739给定每日温度求每个位置后面第一个更高温度出现在几天后。思路单调递减栈栈底到栈顶温度递减遍历时遇到比栈顶温度高的就弹出栈顶并记录答案下标差。这和本题是同一个骨架区别只在弹出时结算什么。这类题目总结下来就是四个要素维护的单调方向、触发弹出的条件、弹出时计算的公式、左边界取什么。把四个要素想清楚所有单调栈题基本都是一样的解。6. 实测中的坑调试方法、边界用例与踩坑实录6.1 最容易翻车的三个细节第一个坑while循环里写成if。很多人在草稿上演算时觉得遇到矮子弹一次就行但实际可能连续弹出多根高柱子。比如[6, 5, 4]遍历到下标 2 时如果只弹一次高度 6 和 5 都得不到结算结果是错的。必须写成while。第二个坑哨兵数组长度和原数组的映射关系。加入哨兵后原数组下标整体偏移 1。如果你在调试时打印栈里下标发现和原数组下标对不上别慌那是哨兵偏移导致的只要面积计算对就行。第三个坑高度很大时面积可能超过int范围。题目提到的数据里高度上限为 10⁴数量级 10⁵所以理论最大面积高达 10⁹C 和 Java 的int都是 32 位最大值约 2.1 × 10⁹勉强够用但面试时建议直接用long类型避免边界翻车。Python 没有这个问题但你要在解题时体现对溢出风险的意识这一句能在面试里加分。6.2 我的调试三板斧如果你在练习时跑不过某个用例我建议按下述顺序排查。第一板斧模拟小数据。拿[2, 1, 2]这种三元素数组手写栈的进出情况对比代码输出。这个用例虽然简单却能暴露宽度公式的各种边界问题。第二板斧打印栈中内容与结算日志。在弹出分支里加一行打印print(fpop idx{top}, h{heights[top]}, left_idx{stack[-1]}, right_idx{i}, area{heights[top] * (i - stack[-1] - 1)})输出结果和手算结果逐行比对能非常快地定位宽度少 1 或多 1 的问题。第三板斧随机数据对拍。写一个O(n²)的暴力函数比如第一节的写法二在本地随机生成千万个长度为 1~20 的数组反复比对暴力解与单调栈解的结果。一旦发现不一致缩到最小用例再分析。这个对拍方法对任何算法题都通用强烈建议掌握。6.3 面试现场怎么一步步引导出这个解如果这是面试题我建议你按这个顺序阐述思路面试官大概率会顺着你的节奏走先给出暴力解法固定左边界 维护最小值O(n²)。指出暴力枚举的冗余当右边界扩展时区间最小值只会变小而我们又不断重新扫过很多重复计算。提出以每根柱子为最低点向两边扩展的视角把问题转换成求每根柱子的左右边界。接着说左右边界本质是左边第一个小于它的下标和右边第一个小于它的下标——这正是单调栈的标准场景。写出左侧扫描代码再写出右侧扫描代码合并成预处理方案。最后展示哨兵优化的单次遍历写法并主动分析时间空间复杂度。这套流程走下来即使细节中途有小失误面试官也会认为你的算法功底扎实因为你展现了从暴力到优化的思考链路而不是直接背模板。很多候选人上来就默写单调栈问为什么栈是递增的反而说不清这就容易被扣分。6.4 一些个人使用体会这个题我前前后后写过不下三十遍每次重写都会发现新的理解盲点。有一段时间我固执地认为必须先学会两遍遍历的预处理写法再学哨兵优化后来发现对初学者来说直接学哨兵写法反而更容易接受——因为代码短整段逻辑可以一口气看完。对已经能熟练默写哨兵写法的朋友我建议你隔一个月再回来尝试在不看任何参考资料的前提下用两遍遍历法重新写一遍。如果你两遍遍历法也能轻松写对那你对单调栈的理解才是真的过关了。在 LeetCode 上这题有接近一万条题解每种语言、每种风格的实现都有。看十篇不如自己写一遍写一遍不如调试十遍。这道题作为单调栈的母题做透了后面一系列变体能省下大量刷题时间。个人实践下来用单调栈时永远别忘了问自己四个问题栈的方向、触发的符号、结算的公式、左边界来源。这四个问题的答案都对得上思路就一定不会错。