LeetCode热题100里的“柱状图中最大的矩形”题号84是一道让很多人又爱又恨的题。爱是因为它考察的单调栈思想在后续刷题中反复出现恨是因为如果你没理解单调栈的触发时机光看题解代码很容易看懂一自己动手写就到处出错。我用Java复现过不少经典题目这道题在面试里被问到的频率非常高值得花力气彻底吃透。这道题的暴力解法很直观但O(n^2)在大数据量下根本跑不动。单调栈解法能把复杂度压到O(n)但理解门槛确实存在。这篇文章我会从暴力解讲起再一步步拆解单调栈为什么能省掉大量重复计算最后给出可直接复用的Java实现和完整模拟过程并列出我实际踩过的坑。无论你是刚开始刷题还是想巩固栈类题型这篇应该都能帮到你。1. 问题本质与暴力解的思维起点1.1 这道题到底在问什么题目本身不复杂给定一个非负整数数组heights每根柱子的宽度固定为1求柱状图里能画出的最大矩形面积。注意矩形必须完全落在柱状图内部不能靠悬空来增加面积。比如输入[2,1,5,6,2,3]最大面积是10来自下标2和3这两根柱子高度为5、宽度为2。很多人第一次看到题目会觉得“最大矩形的高度肯定等于某根柱子的高度”。这句话是对的而且正是整道题的钥匙。如果某个矩形的高度低于它覆盖的所有柱子的高度你完全可以把矩形抬高直到顶到某一根柱子的顶部面积只会变大不会变小。所以解题时不需要考虑任意高度只需要以每一根柱子的高度作为候选矩形高度去尝试。那难点在哪对于一个高度为h的柱子它能画出的最大矩形宽度取决于它左边第一个比它矮的柱子和右边第一个比它矮的柱子。两个方向都得找。如果沿用普通枚举思路找到这两个边界需要往左右两边分别扫描平均下来每根柱子要扫半个数组这就是O(n^2)的来源。1.2 暴力解法为什么不够用先给一个暴力写法感受一下public int largestRectangleAreaBrute(int[] heights) { int n heights.length; int ans 0; for (int i 0; i n; i) { int minH heights[i]; for (int j i; j n; j) { minH Math.min(minH, heights[j]); ans Math.max(ans, minH * (j - i 1)); } } return ans; }这版代码以i为左边界向右扩展一边扩展一边维护区间最小值宽度就是j-i1。如果数组长度是100没问题如果长度到10万循环次数接近50亿Java在判题环境下肯定超时。还有一种常见优化叫“中心扩散”以每根柱子为中心向左右两边扩展直到碰到比它矮的柱子然后计算面积。听起来聪明一点但最坏情况比如高度是[1,2,3,4,...,n]时第n根柱子要向左边扫n次总复杂度还是O(n^2)。真正的问题在于信息没有复用。中心扩散时每根柱子都在重复寻找“左边第一个更矮的位置”。这些信息其实可以共享一根柱子左边第一个更矮的位置往往就是它左侧某根柱子结算面积时已经确认过的信息。我们需要一个结构把这种“最近更矮点”的信息保留下来。这个结构就是单调栈。1.3 从嵌套循环到“延迟结算”的思维转变我第一次做这道题时一直在想怎么提前知道左右边界。后来才明白不需要提前知道可以在遇到“右边界”的那一瞬间把左边界和面积一起算出来。这种做法叫“延迟结算”当某根柱子还没遇到右边更矮的柱子之前先不计算它的最终面积一旦遇到立刻算算完就不再管它。左边更矮的柱子信息由栈自动维护你不用回头遍历。这个思维转变如果绕不过去后面看代码会非常痛苦。如果你也有类似的感觉我建议你先放下代码用手在纸上模拟几个例子直到你接受“延迟”这件事。2. 单调栈的核心原理2.1 单调递增栈到底维护了什么我们用栈来存柱子的下标并且始终保证从栈底到栈顶对应柱子的高度是严格递增的。也就是说栈顶的柱子一定比栈底的柱子更靠右且更高。怎么维护这个性质从左到右扫描时如果当前柱子高度大于等于栈顶柱子高度直接压栈如果当前柱子高度小于栈顶柱子高度就不断弹出栈顶直到栈顶高度小于等于当前柱子高度再把当前柱子压栈。为什么等于时也可以不弹因为等于说明这个高度平台还没结束等平台遇到真正矮的柱子再一起结算。如果你在等于时也弹逻辑上没错但会多做无用功还容易让代码边界变复杂。栈里存下标而不是存高度是为了计算宽度。下标之间的距离代表柱子数量宽度必须是整数个柱子宽度。如果只存高度值你算出面积却不知道具体覆盖哪些柱子边界很容易算错。2.2 弹出栈顶时左右边界为什么会浮出水面这是整个单调栈最核心的一步。假设当前扫描到下标i当前柱子高度是h[i]它比栈顶柱子高度小说明栈顶柱子遇到了“右边第一个更矮的柱子”。现在弹出栈顶下标p以heights[p]作为矩形高度。右边界已经明确是i因为从p1到i-1之间的柱子高度都不小于heights[p]否则p早就被弹出了。左边界是谁是弹出后新的栈顶下标q。为什么q就是左边第一个更矮的位置因为栈里保证从底到顶高度递增所以h[q] h[p]而q又是p下面离p最近的下标。至于p上面曾经有过的柱子它们高度都大于等于h[p]已经被弹出结算了。结论很简单以h[p]为高度的最大矩形左边界右边第一个下标是q1右边界左边最后一个下标是i-1宽度就是i - q - 1。这个过程还有一个很漂亮的性质因为所有高度大于等于h[p]的柱子都已经被处理过了所以p弹出这一刻就是它最后一次参与面积计算。2.3 为什么说每根柱子只会被处理一次入栈一次、出栈一次中间没有任何重复扫描。这跟暴力解法的最大区别是暴力解法中一根柱子可能被当作左边界、右边界、最小高度重复算很多次而单调栈里每根柱子的“最大矩形”只结算一次。用摊还分析的说法虽然while循环可能一口气弹很多根柱子但这些柱子都是之前入栈的总弹出次数不超过总入栈次数。所以整个算法循环总次数是O(2n)也就是O(n)。这个复杂度证明不用背理解“每个下标只进出栈一次”就够了。3. Java实战两种实现的完整拆解3.1 带哨兵写法我最推荐的一种先写最推荐的版本在数组前后各补一个高度为0的哨兵。我自己面试如果写这道题大概率会默写这个版本因为它把边界处理得干干净净。public int largestRectangleArea(int[] heights) { int n heights.length; int[] h new int[n 2]; for (int i 0; i n; i) { h[i 1] heights[i]; } h[0] 0; h[n 1] 0; DequeInteger stack new ArrayDeque(); stack.push(0); int ans 0; for (int i 1; i n 2; i) { while (h[i] h[stack.peek()]) { int height h[stack.pop()]; int width i - stack.peek() - 1; ans Math.max(ans, height * width); } stack.push(i); } return ans; }h数组长度为n2把原数组整体右移一位。头部补0、尾部补0。尾部的0会在最后一次循环中扮演“右边的矮柱子”把栈里所有正常柱子全部弹出来头部的0保证栈永远不会弹空因为正常柱子高度都大于等于0扫描到末尾0时while条件“0 0”为false哨兵不会出栈。循环从1开始因为第0号元素是头部哨兵。while的判断条件用的是严格小于。当当前高度小于栈顶高度时说明栈顶柱子的右边界出现了。弹出栈顶并计算面积。关键点在于“弹出后栈一定不为空”因为栈底有头部哨兵所以你可以直接stack.peek()拿到左边界。如果你忘了这个前提就会对“栈会不会空”提心吊胆逻辑容易乱。关于用ArrayDeque还是LinkedList作为一个栈使用ArrayDeque底层是循环数组push和pop都是O(1)而且没有同步开销。LinkedList虽然也能当栈但每个节点是对象内存和速度都差一点。刷题时用ArrayDeque就行。3.2 不带哨兵的等价写法如果你不想在数组上做手脚也可以用不补哨兵的版本public int largestRectangleArea(int[] heights) { int n heights.length; DequeInteger stack new ArrayDeque(); int ans 0; for (int i 0; i n; i) { int cur (i n) ? 0 : heights[i]; while (!stack.isEmpty() cur heights[stack.peek()]) { int height heights[stack.pop()]; int left stack.isEmpty() ? -1 : stack.peek(); int width i - left - 1; ans Math.max(ans, height * width); } stack.push(i); } return ans; }这个版本里i等于n的时候手动造出一个高度0相当于隐性哨兵。由于没有显式栈底弹出之后需要判断栈是否为空。左边界为空时是-1宽度就是i代表矩形从下标0一直延伸到i-1。两个版本结果一样。我个人的习惯是面试中写带哨兵版本因为代码短、不容易漏边界如果是给别人讲原理用不带哨兵的版本更直观因为它把“空栈处理”写出来了读者更容易理解左边界到底是谁。3.3 复杂度分析与一个你容易忽略的细节时间复杂度O(n)主循环一共走n2次while循环内部的操作总数不超过n因为每个元素最多弹一次。空间复杂度O(n)栈里最多存n个元素发生在柱子高度严格递增、扫描到末尾之前的情况。如果数组全为正数单调递增栈会把所有下标都留着直到最后一个哨兵才清空。有同学会问能不能把空间优化到O(1)这道题标准解法就是O(n)空间。听起来单调栈只用一个栈似乎比“左右扫描”要省但左右扫描如果用两个数组预处理左边界和右边界同样也是O(n)空间。如果硬要O(1)得依赖“柱子高度范围有限”这类特殊前提属于歪门邪道不推荐。还有一个细节值得单独说一下带哨兵版本里如果你在复制数组时直接修改了传入的heights可能会影响后续使用。比如你本来想保留原数组做其他操作结果发现它被你悄悄改成了[0, 2, 1, 5, 6, 2, 3, 0]。所以更稳妥的做法是像我一样新建一个h数组不要动原始输入。4. 手把手模拟一遍完整流程4.1 用输入[2,1,5,6,2,3]逐步走一遍这一步建议你也跟着手动演算。只有把过程在脑子里过一遍你才能真正理解“右边界出现”的那一瞬间。准备阶段h [0, 2, 1, 5, 6, 2, 3, 0]栈初始为[0]表示头部哨兵。i1h[1]22 h[0]0否。压栈栈变成[0,1]。i2h[2]11 h[1]2是。弹出下标1height2新栈顶是0width2-0-11面积2继续判断1 h[0]0否。压栈下标2栈变成[0,2]。这一步的含义是柱子2遇到了右边更矮的柱子1所以以2为高度的最大矩形只有它自己面积就是2。i3h[3]55 h[2]1否。压栈栈变成[0,2,3]。i4h[4]66 h[3]5否。压栈栈变成[0,2,3,4]。i5h[5]22 h[4]6是。弹出下标4height6新栈顶3width5-3-11面积6继续2 h[3]5是。弹出下标3height5新栈顶2width5-2-12面积10继续2 h[2]1否。压栈下标5栈变成[0,2,5]。这一个大循环是整道题的精华。柱子6先遇到右边柱子2以6为高度的矩形宽度只能是1柱子5随后也遇到右边柱子2但它的左边界不是5自己而是栈里现在栈顶的下标2高度1所以宽度是5-2-12面积是10。i6h[6]33 h[5]2否。压栈栈变成[0,2,5,6]。i7h[7]00 h[6]3是。弹出下标6height3新栈顶5width7-5-11面积3继续0 h[5]2是。弹出下标5height2新栈顶2width7-2-14面积8继续0 h[2]1是。弹出下标2height1新栈顶0width7-0-16面积6继续0 h[0]0否。压栈下标7。最后答案是10。4.2 模拟结果背后的几个验证点你可以对照刚才的流程检查几个关键面积。以高度5的矩形为什么宽度是2因为左边第一个矮于5的柱子是下标2高度1右边第一个矮于5的柱子是下标5高度2中间是下标3和4两根柱子宽度正好2。以高度1为高的矩形为什么宽度是6因为它左边和右边都没有更矮的柱子所以横跨整个数组。这个面积的结算被放到了最后因为高度1一直压在栈里直到末尾哨兵0出现才触发。注意这里用末尾0判断0 1所以触发宽度为6。为什么不出现宽度为3、高度5之类的更大面积因为下标2的高度只有1它把左半边整体高度限制住了下标5的高度只有2它把右半边高度限制住了。单调栈会自动发现这种“被矮柱子分割”的结构。5. 边界条件与典型错误避坑指南5.1 空数组和单元素数组空数组返回0即可。单元素数组像[5]带哨兵版本会得到[0,5,0]流程是i1压栈i2触发弹出height5width1面积5。如果你用的是不带哨兵版本结尾清理也必须算进去。我之前见过有同学在循环里手动清空栈时忘了左边界取-1导致宽度少加1输出4而不是5。边界一定要测试。5.2 高度相等时该不该出栈输入[2,2,2]的最大面积是6。前面已经说过用严格小于时三个2会连续压栈直到末尾0才依次弹出最终正确结算用小于等于时也会正确。那为什么我更推荐严格小于因为“严格小于”符合“右边第一个更矮柱子”的定义。等于时不出栈等于平台会被视为一个整体只在最后统一结算。这样减少无谓弹出更重要的是后续做二维最大矩形等变形题时等于处理不当可能引入重复计算。5.3 栈里剩余元素怎么算不带哨兵版本最经典的连环坑数组本身是递增的比如[1,2,3,4]。扫描过程中while一次都没执行所有下标都压进栈。循环结束后如果不额外处理答案是0。处理方式是在循环结束之后把栈里剩余元素依次弹出此时它们的右边界都是数组末尾n左边界还是各自下面那个栈元素。对于递增数组最后弹出的最高柱子比如高度4只能宽度1高度3的宽度是2依次类推。带哨兵版本没有这个问题因为末尾0会在主循环里把所有柱子都弹完。这也是我反复推荐哨兵版本的最大原因之一。5.4 常见错误速查表错误类型具体表现修复方式忘清空栈递增数组输出0使用尾部哨兵0或在循环后补while清理左边界取错空栈时用0而不是-1带哨兵版本保证栈底有0不带哨兵版本判空宽度公式写错写i - peek而不是i - peek - 1牢记宽度是开区间(i-1) - peek等于时也弹出效率降低但答案不变建议只在严格小于时弹出用LinkedList当栈性能稍差但可接受用ArrayDeque原数组被修改带哨兵版本直接改传入数组新建数组别动原始输入表格最后一行是我自己踩过的坑。如果你直接拿原数组往头部插0要么用ArrayList做插入要么干脆新建数组。直接修改原数组会影响后续使用也容易在debug时产生困惑。6. 从这道题走向整个“单调栈”家族6.1 接雨水LeetCode第42题和84题经常被一起提起。接雨水的思路是维护一个单调递减栈当遇到比栈顶高的柱子时说明当前可能形成凹槽弹出栈顶作为底部再检查新栈顶和当前高度取较小值减去底部高度就是该处能接的雨水高度。它跟84题相反的地方是84题是“遇到更矮的柱子就结算高柱子的最大矩形”接雨水是“遇到更高的柱子就结算凹槽”。一个找右边更矮的一个找右边更高的。方向恰好相反但套路一脉相承。如果你能独立把84题和42题都讲清楚面试官基本可以确认你对单调栈有深入理解。6.2 二维最大矩形LeetCode第85题“最大矩形”是84题的升级。给你一个m行n列的01矩阵找出全1矩形的最大面积。做法是以每一行为底计算该行往上的连续1高度得到一个heights数组然后对每个heights调用本题的largestRectangleArea。这样二维问题就变成了m次一维问题总复杂度O(m*n)。这个转化非常值得做一遍因为你会发现复用程度很高。我当时刷这道题的时候直接把84题的代码抽出来当工具方法主函数只负责把矩阵逐行转成高度数组代码量瞬间少了一半。6.3 每日温度和其他“下一个更大/更小”问题热题100里还有“每日温度”找每个位置右边第一个比它温度高的日子。思路是维护一个单调递减栈从栈底到栈顶温度递减当当前位置温度比栈顶高时弹出栈顶并记录答案。这个问题的答案是下标差不是面积但栈的用法和84题一样都是在下标入栈后遇到满足条件的当前元素才批量结算。这类问题在题目里通常叫“下一个更大元素”或“下一个更小元素”。考试频率不低一旦你掌握单调栈后它们会变得非常简单。很多初学者看到“下一个更大元素”会想当然地去用双重循环小数据能过大n就超时。6.4 如何培养单调栈直觉我的经验是不要把单调栈当成一个“高级数据结构”去背把它理解成“延迟结算 最近边界”的组合。什么时候会用到题目要求寻找每个元素左边或右边第一个更大/更小元素时题目里出现“连续的某些元素被最值卡住”这类描述时需要对很多子数组求最大值或最小值贡献而暴力枚举区间又不现实时。一旦识别出这些模式单调栈就是非常自然的工具。建议至少手动模拟三道经典题柱状图中最大的矩形、接雨水、下一个更大元素。模拟时不要只盯着答案要把每次弹出时“为什么现在能结算”“左边界是谁”讲给自己听。讲得出来才算真的会了。我个人第一次看这道题题解时连续几天都处于“看懂但写不出来”的状态。后来我用最笨的方法把[2,1,5,6,2,3]的每一步入栈出栈都画在纸上画到第5步的时候突然就通了。现在回头看单调栈之所以让人觉得难是因为它跟你平时写嵌套循环的直觉不太一样你不再同时枚举左右边界而是让栈替你记住左边边界只等着右边边界出现。一旦你适应了这种“等”的节奏后面再刷任何单调栈题都会顺很多。如果你现在正卡在这道题上我建议你别急着背代码先从模拟开始。