刷LeetCode刷到单调栈这一块的时候很多人的第一反应是——这不就是个栈吗然后直到碰见每日温度和柱状图中最大的矩形这两道题才明白事情没那么简单。我当年也被这两道题卡了不少时间后来把单调栈的套路理顺了回头再看这一类题基本就是一套模板走天下。单调栈听起来高大上本质上就是普通栈加了一条纪律栈内元素保持单调。要么从栈底到栈顶严格递增要么严格递减破坏单调性的元素在入栈前先弹出。就靠这一条纪律能把一堆看起来需要O(n²)的题压到O(n)而且代码短到让人怀疑人生。这篇文章不是把题解抄一遍而是把为什么要这么做出栈时到底在结算什么边界条件为什么这么处理这些底层逻辑讲透。适合刚好卡在单调栈题上、想彻底搞定这一类题目的朋友。我会用两道最经典的题——LeetCode 739每日温度和LeetCode 84柱状图中最大的矩形——把单调栈从思路到代码到踩坑点完整过一遍。1. 单调栈到底是个什么东西从暴力解法到单调栈的演进1.1 一个最朴素的问题场景先抛开题目想一个生活场景。你在排队买奶茶队伍里每个人的身高都不一样你想知道队伍里每个人右边第一个比自己高的人离自己有多远。站在队伍前面的人往后看一眼扫过去找到第一个比自己高的可能要扫很久。最笨的办法就是每个人都往后扫一遍n个人就是O(n²)。每日温度就是这么个问题给一个数组记录每天温度要输出每个位置距离下一个更高温度的天数。柱状图中最大的矩形也类似每个柱子要找到左右两边第一个比它矮的柱子来确定自己能扩展的宽度。这类问题有个共同结构对序列中每个元素找左边或右边第一个比它大或比它小的元素。这就是下一个更大元素问题族单调栈就是为这类问题量身定制的解法。1.2 暴力解法的痛点与单调栈的思路起源暴力解法为什么慢因为信息没有复用。第i天找右边第一个更高温度第i1天又从头找一遍每一次都是独立扫描之前扫描过的信息全扔了。单调栈的思路是把已经处理过但还没找到答案的元素暂存起来。元素在栈里排成一列栈底到栈顶保持单调性。新元素来的时候如果它破坏了单调性就把栈顶元素弹出去弹出去的那一刻就是栈顶元素可以结算答案的时刻。为什么因为新元素就是当前栈顶右边第一个不满足单调性的元素换个说法——它就是栈顶在找的那个下一个更大或更小的元素。每个元素入栈一次、出栈一次所以总复杂度O(n)。这就是单调栈厉害的地方用空间换时间把暴力重复扫描变成了一次遍历里的即时结算。1.3 单调栈的两种形态单调递增栈和单调递减栈从栈底到栈顶如果元素值递增叫单调递增栈递减则叫单调递减栈。但要注意具体用递增还是递减取决于题目要找的是下一个更大还是下一个更小。找下一个更大元素维护单调递减栈。当前元素比栈顶大时栈顶元素找到答案并弹出。找下一个更小元素维护单调递增栈。当前元素比栈顶小时栈顶元素找到答案并弹出。找左边边界弹出栈顶后新的栈顶就是左边边界。因为栈是单调的新栈顶是栈里离当前元素最近且满足单调关系的元素。记不住方向的同学我有个笨办法直接想谁该被弹出去——如果当前元素比栈顶更符合大或小的特征那栈顶就该走人了。写得多了自然就记住了。注意这里说的单调栈一般默认存的是下标不是元素值。原因后面细说先记住这个习惯。2. 经典题目一每日温度LeetCode 7392.1 题目理解与暴力解法的复杂度题目给一个整数数组temperatures表示每天气温返回等长数组answeranswer[i]表示第i天后需要等多少天才能等到更高的温度。如果之后都不存在更高的温度填0。拿例子过一遍temperatures [73, 74, 75, 71, 69, 72, 76, 73]。第0天73第1天74就更高答案1。第1天74第2天75更高答案1。第2天75要等到第6天的76间隔4。第3天71第5天72更高答案2。第6天76后面没人更高答案0。暴力解法就是双重循环第i天往后扫到第一个更大的元素算间隔。最坏情况比如温度单调递减再单调递增复杂度O(n²)。n到10的5次方就会超时所以必须优化。2.2 单调栈解法核心记录下标而不是记录温度核心思路是从左往右遍历温度数组维护一个单调递减栈栈里存的是下标。为什么存下标因为答案要求的是间隔天数存下标才能算i - stack.peek()光存温度没法算距离。遍历到temperatures[i]时只要栈不空而且当前温度高于栈顶下标对应的温度说明栈顶元素已经等到了它右边第一个更高温度此时弹出栈顶topanswer[top] i - top。这个比较可能连续触发因为当前温度可能比栈里好几个都高每个被踢出去的都当场结算。当前温度踢不动别人之后把i入栈等待它自己的下一个更大元素到来。为什么这样不会漏因为栈里从栈底到栈顶温度是递减的越靠近栈顶越年轻也越低。任何被弹出的元素都是被右边第一个比它大的带走的还没被弹出的右边还没出现更大的。全部遍历完后栈里剩下的元素说明它们右边没有更高温度了answer保持0即可。2.3 Java代码实现与逐行讲解public int[] dailyTemperatures(int[] temperatures) { int n temperatures.length; int[] answer new int[n]; DequeInteger stack new ArrayDeque(); for (int i 0; i n; i) { // 当前温度比栈顶温度高栈顶找到下一个更高温度 while (!stack.isEmpty() temperatures[i] temperatures[stack.peek()]) { int idx stack.pop(); answer[idx] i - idx; } stack.push(i); } // 栈里剩下的右边没有更高温度answer保持0 return answer; }代码短到有点不像O(n²)的优化但它确实把每个元素最多入栈一次、出栈一次。这里用ArrayDeque而不是Stack是因为Java的Stack继承Vector有同步开销刷题建议用ArrayDeque。逐段说下细节while循环里的判断条件是当前温度 栈顶温度才弹出。注意是严格大于因为题目要的是更高温度等于不算更高。如果把大于写成大于等于等于的情况下栈顶就提前结算了答案会偏小。弹出的idx是栈顶下标栈顶下面的新栈顶就是idx左边第一个比它高的候选——不过这道题不需要用它所以不用管。当前温度在while结束后入栈。此时栈里所有温度都大于等于当前温度栈的单调递减性质保持住了。整个流程走一遍遍历到75时栈里是[73的下标0, 74的下标1]。75先弹74answer[1]1再弹73answer[0]1然后把75入栈。之后71、69入栈轮到72时把69和71都弹了。每一步都符合预期。2.4 一道题看透出栈即结算很多人看单调栈代码最懵的就是为什么弹栈的时候顺便结算。前面说了因为当前遍历到的元素就是栈顶右边第一个更大元素。这个结论的成立依赖于栈的单调性栈里是单调递减的所以从栈顶往下都还没找到更大的当前元素是第一个突破栈顶的元素对栈顶来说就是第一个更大的。对栈里更底层的元素来说当前元素也是它右边第一个比它大的吗不一定。比如栈里从底到顶是[70, 71, 69]当前元素73。69先被弹出接着71被弹出70也被弹出。73同时是69、71、70的右边第一个更大元素吗69是71是70也是。因为栈是单调递减的73比栈顶大就必然比栈里所有元素都大。所以while循环一口气把能踢的全部踢干净每个被踢的结算结果都是对的。想明白这一点单调栈就通了每个元素在入栈后等待自己被踢出去的那一刻踢它的人就是它的答案来源。3. 经典题目二柱状图中最大的矩形LeetCode 843.1 题目分析与暴力思路的瓶颈题目给一个非负整数数组heights每个柱子宽度为1求这些柱子能组成的最大矩形面积。比如heights [2, 1, 5, 6, 2, 3]最大矩形是高度5、宽度2的那块区域面积10。暴力思路通常是枚举左右边界计算区间最小高度乘以宽度O(n²)。另一种暴力是固定每个柱子作为矩形高度向左右两边扩展直到遇到比它矮的柱子。这个思路方向是对的但每次扩展都逐个比较整体还是O(n²)。单调栈要做的就是快速找到每个柱子左右两边第一个比它矮的位置从而算出它作为高度的最大宽度。3.2 单调栈解法核心以每个柱子为高度的左右边界关键结论对于一个柱子heights[i]如果它能作为矩形高度那这个矩形的左右边界就是左边第一个比它矮的柱子和右边第一个比它矮的柱子。矩形宽度 right - left - 1面积 heights[i] * (right - left - 1)。为什么因为矩形要想以heights[i]为高里面不能有比它矮的柱子边界自然就是两头第一根更矮的柱子。所以题目转化为对每个i找左边第一个更矮的下标left找右边第一个更矮的下标right。这正好是单调栈的拿手戏。这里用单调递增栈。从左往右遍历当前柱子高度比栈顶矮时栈顶柱子要出栈此时当前遍历到的位置i就是栈顶柱子右边第一个更矮的位置即right i。弹出栈顶后新的栈顶就是栈顶柱子左边第一个更矮的位置因为栈是单调递增的弹出后下面的元素一定比它矮且位置在它左边即left 新栈顶。结算面积heights[top] * (i - newTop - 1)。这个逻辑和每日温度正好镜像对称一个用递减栈找更大一个用递增栈找更小。3.3 代码实现与边界处理哨兵技巧边界问题是这道题最大的坑。两个场景遍历结束后栈里还有柱子。它们的右边没有更矮的柱子了但它们的矩形面积还没结算。栈空的时候弹出栈顶没有新栈顶可以当left。解决办法是加哨兵在heights数组两端各补一个0。开头补0保证栈永远不会为空因为0比所有非负整数都小永远不会出栈结尾补0因为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[n1] 0 作为哨兵 DequeInteger stack new ArrayDeque(); stack.push(0); // 哨兵先入栈 int maxArea 0; for (int i 1; i n 1; i) { while (h[i] h[stack.peek()]) { int top stack.pop(); int left stack.peek(); int area h[top] * (i - left - 1); maxArea Math.max(maxArea, area); } stack.push(i); } return maxArea; }注意我用的是h[i] h[stack.peek()]才弹出严格小于。为什么不是小于等于因为高度相等的柱子left边界如果选成相等的柱子矩形宽度会被压缩但相等高度之间完全可以并入同一个矩形里。所以相等时不出栈让后面的柱子把它带出去最终由最右边那个相等高度的柱子结算宽度才是完整的。这属于容易写错但答案也没差的细节面试时最好能主动说出来。3.4 手动模拟一遍整个流程把面积算明白用heights [2, 1, 5, 6, 2, 3]加上哨兵后数组是[0, 2, 1, 5, 6, 2, 3, 0]。我直接列一个模拟表追踪栈的变化和结算时机当前遍历下标ih[i]操作出栈元素top左边界left结算面积00入栈---12入栈---21h[2] h[1]弹出11left02 * (2-0-1) 221入栈---35入栈---46入栈---52h[5] h[4]弹出44left36 * (5-3-1) 652h[5] h[3]弹出33left25 * (5-2-1) 1052入栈---63入栈---70h[7] h[6]弹出66left53 * (7-5-1) 370h[7] h[5]弹出55left22 * (7-2-1) 870h[7] h[2]弹出22left01 * (7-0-1) 6最大面积是10来自高度5、宽度2的矩形。注意到这个模拟里每个柱子的左边界居然各不相同有的直接被哨兵兜底。这就是哨兵的价值没有左边界的left直接取0没有右边界的最后被末尾的0逼着全部结算。4. 单调栈的通用套路与变体题4.1 识别特征什么样的题该用单调栈我总结了一个简单的判断清单满足两条以上就可以考虑单调栈需要找某个元素左边/右边第一个比它大或小的元素。题目里有距离面积跨度这类关键词意味着需要位置信息。数据规模在10的5次方级别暴力O(n²)过不了。画图之后发现元素之间存在一种你被谁挡住、你能扩多远的依赖关系。最典型的识别信号是每个元素的答案由下一个更大或更小的元素决定。遇到这种结构别急着写双重循环先想想单调栈。4.2 单调栈的模板总结一套代码打天下把两道题的代码放一起看骨架几乎一样DequeInteger stack new ArrayDeque(); for (int i 0; i n; i) { while (!stack.isEmpty() 当前元素与栈顶元素破坏单调性) { int top stack.pop(); // 结算top的答案 // 可能用到当前元素i作为右边界 // 可能用到弹出后的新栈顶stack.peek()作为左边界 } stack.push(i); }区别只有三处破坏单调性的条件大于还是小于严格还是不严格。结算时用当前元素i还是用新栈顶还是两者都用。是否需要处理栈里剩余元素或者用哨兵避免。这个模板适用的不只是上面两道题几乎所有下一个更大元素系列的变种题都能套。4.3 常见变体题从基础题到进阶题的路子LeetCode 42 接雨水经典难度的变体也是用递减栈。入栈和出栈时机一样但面积结算用的是被夹出来的水多了一个计算左右边界之间距离和高差的步骤。强烈建议做完84再做42你会发现思路复用得极其顺畅。LeetCode 496 下一个更大元素 I数组子集场景配合HashMap记录nums2中每个元素的下一个更大元素。LeetCode 901 股票价格跨度在线场景输入一个价格返回连续小于或等于当前价格的天数。本质还是单调栈只是把数组遍历换成了动态追加。LeetCode 316 去除重复字母这题表面上是字符串去重实际也是在维护一个字典序尽可能小的单调栈只是比较对象换成了字符还加了出现次数约束。LeetCode 962 最大宽度坡找j - i最大值要求i j且A[i] A[j]左端点用单调递减栈存候选右端点从右往左扫描。刷完这些再看单调栈题基本就是送分题了。做题顺序建议739每日温度 - 496下一个更大元素 - 84柱状图中最大的矩形 - 42接雨水 - 316去除重复字母一步步来。5. 常见问题与排查技巧实录5.1 栈空、相等元素这些边界条件到底怎么处理栈空84的left需要用新栈顶如果弹出后栈空了left就取-1因为不存在更矮的左边界这时宽度就是i。这个处理在代码里就是加哨兵让栈永远不会真的空。强烈建议在数组前后补哨兵0或极大值比你写一堆if判空要稳得多。我见过太多人在边界条件上写错一两个方向直接整题崩掉。相等元素739里温度相等不算更高用严格大于出栈。84里高度相等不急着出栈用严格小于出栈。如果拿不准一律用严格因为第一个更大或更小通常定义就是严格意义。5.2 为什么要存下标而不存值这个问题值5分很多人第一版代码写成把值塞进栈里然后发现没法算间隔天数或者矩形宽度。原因很简单题目要的是位置关系值只能告诉大小关系。下标是值的增强版它同时携带了位置和值两项信息通过heights[stack.peek()]拿值、通过i - stack.peek()算距离。所以单调栈的标配是存下标拿值要用数组去查。我最初写739的时候也犯过这个错误存了一堆温度值最后算间隔时傻眼了还要再开一个Map去反查下标绕了一大圈才明白栈里直接存下标是最优选择。5.3 调试技巧利用打印栈和答案数组快速定位问题单调栈代码短但逻辑绕调试起来最有效的方法就是打印中间状态。在每个循环里打印当前下标、当前值、栈内容、答案数组一眼就能看出来是哪里弹错、哪里结算错、哪里边界处理不对。可以写个简单的调试辅助private void debug(int i, int value, DequeInteger stack, int[] result) { System.out.println(i i , val value , stack stack , topVal (stack.isEmpty() ? null : heights[stack.peek()]) , result Arrays.toString(result)); }实测中80%的单调栈bug是因为while循环条件方向写反20%是哨兵缺失导致栈空。这两个问题都能通过打印快速发现。还有一个零成本的办法把例子代入代码手动跑一遍每次只操作一个例子比如84题用[2,1,5,6,2,3]别偷懒跑完基本就稳了。5.4 实际踩过的坑和个人经验我踩过最典型的坑是84题第一个版本没有哨兵然后在循环里狂写if(stack.isEmpty())分支处理左边界的逻辑又臭又长最后面积还少了1。加哨兵之后代码几乎砍掉一半正确率直接拉满。另外一个容易忽略的点是哨兵值的选择不是所有题都补0有些题哨兵需要补极大值比如找下一个更小元素时左边界哨兵要补极大值才不会提前弹出。用之前先想想哨兵会不会影响弹出条件。做这类题我还有一个体会画图比写代码重要。把柱状图老老实实画出来标出每个柱子左右第一根更矮的柱子面积公式自己就能推导出来。画的次数多了单调栈的出栈即结算就变成肌肉记忆了。尾记如果你刚接触单调栈有点懵别急我一开始也是这样。建议先把739和84两道题亲手过三遍——第一遍照着写、第二遍只看思路写代码、第三遍隔天默写。等你熟悉了这套模板再做42接雨水、316去除重复字母这些变体会发现脑子里会自动把问题映射成入栈、出栈、结算三个动作。最后分享一个小技巧想检验自己是不是真懂了把单调递减栈改成单调递增栈把找更大改成找更小看看代码里哪些条件要变、哪些结算逻辑要变。能独立改出来说明你是真的把这个数据结构拿下了。单调栈不是一个高不可攀的技巧它只是给每个人都在找自己右边第一个更高的人这件事安排了一个高效的排队机制。想通这一层以后看到这类题你就能笑着动手了。