这题我刷了整整三遍才算真正吃透。第一次看见“每日温度”的时候心想这不就是两层循环暴力扫一遍的事结果一提交超时得明明白白。后来才意识到这道题根本不是考你循环嵌套写得多熟练它真正想让你掌握的是单调栈这个数据结构。标题里写的“1.20单调栈每日温度”也就是我刷题笔记里专门给单调栈开的一节拿这道经典题来切入再合适不过了。先给没见过的朋友说下这道题在讲什么给你一个每天温度的数组比如[73, 74, 75, 71, 69, 72, 76, 73]让你返回一个新数组里面每个位置的值表示“要等多少天才会出现比这一天更高的温度”。等不到就填0。比如第0天是73度第1天74度就比它高了所以结果是1但第4天是69度要等到第5天72度才算更高所以结果也是1。套用到每个位置输出的就是[1, 1, 4, 2, 1, 1, 0, 0]。这道题适合谁适合刚开始刷算法题、卡在“暴力解通过不了”阶段的人也适合那种知道单调栈这个名字、但一直没搞懂它到底怎么用的人。这篇文章我会从暴力解法讲起把单调栈的原理掰开揉碎给出可以直接复用的代码写法顺便把调试过程中最容易踩的坑一起说了。1. 题面与思路拆解从“等几天”这个直觉问题开始1.1 把题目翻译成大白话“每日温度”其实是在问一个非常生活化的问题今天这个温度接下来还要熬几天才能遇到一个更暖和的日子注意它的条件有两层第一层是温度必须“更高”不是持平也不是更低第二层是去找“最近的”那个更高温度的日子算它们之间隔了几天。这两层条件合在一起本质就是在做一件事对数组中的每个位置找到它右侧第一个比它大的元素记录这个元素和它的距离。这个描述一出来懂一点算法的朋友应该已经嗅到了熟悉的味道——这就是经典的“下一个更大元素”变种题LeetCode 496就是那个题。只不过496要求返回的是一段距离每日温度要求返回“间隔天数”代码上就差一个下标相减。还有一个很容易看漏的细节题目里说的是温度但实际比较是把温度当作数字处理与日期无关。也就是说只要数组内部数值满足关系日期只用来计算距离。数字本身没有单位只是用来做大小比较的。1.2 暴力解法为什么一定超时我当初第一次写的暴力解法很简单两层循环外层循环枚举每一个位置i内层循环从i1开始向右找第一个大于temperatures[i]的数找到就break记录距离找不到就填0。vectorint dailyTemperatures(vectorint temperatures) { int n temperatures.size(); vectorint ans(n, 0); for (int i 0; i n; i) { for (int j i 1; j n; j) { if (temperatures[j] temperatures[i]) { ans[i] j - i; break; } } } return ans; }这个写法的思路老实说没问题逻辑也对但一旦数据量上来就完蛋。假设数组长度是n最坏情况下温度序列单调递减也就是每天都比前一天冷比如[100, 99, 98, ..., 1]。这种情况下内层循环每次都把后面的元素全部扫完还找不到更大的所以两两组合都要跑一遍总操作次数接近n²/2时间复杂度O(n²)。当n是10万级别的时候n²就是百亿量级在标准OJ上跑1秒基本是做梦。就算你的本机CPU很强也会明显等上好几秒。所以这道题的存在意义某种意义上就是逼你放弃暴力枚举。解法时间复杂度空间复杂度是否能通过大数据测试暴力双重循环O(n²)O(1)在10万级数据下严重超时单调栈O(n)O(n)顺畅通过1.3 题目隐含的三种情况总结在所有测试数据里每个位置只可能出现三种结果右侧存在更高温度返回最近更高温度与当前日期的差值。右侧不存在更高温度返回0。温度相等的情况不算“更高”必须严格大于。这三种情况看起来简单但在写单调栈的时候分支判断稍一马虎就会错。很多人是在“相等”这个边界上栽的跟头后文我会专门说到这个细节。2. 单调栈的直觉来源为什么栈这个结构天生合适2.1 一个“回调任务”的视角我第一次想明白单调栈能用在什么场景是通过一个厨师做菜的类比。假设你手头有一堆外卖订单每单上都写着出餐时间你先接到的订单放在桌上的文件筐里后到的订单往上一放。如果某一刻突然来了一个“紧急加急单”你会从最上面开始往下翻找到第一个时间比它晚的订单。栈就是这样一个文件筐你只从最上面拿东西。而“每日温度”这个问题恰恰可以理解成“每来一个更大的温度就要把前面所有比它小的温度结算掉”。这副“后进先出”的结算顺序和栈在结构上完全一致。2.2 单调性栈内元素的排列规律单调栈就是在普通栈的基础上维持一种“从栈底到栈顶单调递增或递减”的特征。放在“每日温度”里我们维持的是一个从栈底到栈顶递减的栈。递减意味着栈顶元素是当前栈里最小的那个注意这里说的是栈内保留的“温度值”或“温度对应的下标”后文我统一探讨。为什么非要把栈维持成递减的因为当我们从左到右遍历数组时一旦遇到了一个比栈顶元素温度更高的日子栈顶元素作为“等待更高温度的人”就可以立马结算出它的答案。而这个结算顺序天然是离当天最近的一个未结算元素恰恰是由栈顶元素提供的。如果栈不是递减的栈顶元素就不一定是“最近等待结算”的人逻辑就乱了。2.3 栈里存下标还是存温度新手最容易纠结的一个点是栈里到底放数组的值还是放数组的下标在“每日温度”这道题里答案很明确必须存下标。原因很简单我们最终要计算的是间隔天数也就是两个日期下标之差。如果不存下标光有温度值算不出距离。而且当温度值相同的时候光看数值也无法区分是哪个位置。所以即使你在弹出栈顶元素时能用temperature[st.top()]取到温度也要把下标本身入栈。这里有一个可以举一反三的经验凡是需要“求距离”“求区间长度”“求下标差”的问题栈里存下标基本是通用做法如果题目只要求比较大小、不涉及位置那也可以直接存值但那样的题目很少出现在“单调栈”系列的主要练习题里。3. 两种正确写法实操正向遍历与反向遍历3.1 正向遍历的解法推荐重点掌握正向遍历的思路是让栈里保留“还没有找到更高温度的日子的下标”。每来一个新日子就用它的温度去和栈顶日子的温度比较如果栈顶日子的温度低于新日子说明栈顶日子的“更高温度”出现了立刻出栈并计算距离。vectorint dailyTemperatures(vectorint temperatures) { int n temperatures.size(); vectorint ans(n, 0); stackint st; // 栈里存下标温度从栈底到栈顶递减 for (int i 0; i n; i) { while (!st.empty() temperatures[i] temperatures[st.top()]) { int idx st.top(); st.pop(); ans[idx] i - idx; } st.push(i); } return ans; }这个代码的过程我来手推一遍这样你才能真正理解栈里发生了什么。以[73, 74, 75, 71, 69, 72, 76, 73]为例i0温度73栈空直接把0压栈。栈内状态[0(73)]i1温度74stack顶是0温度7374所以0出栈ans[0]1-01。然后栈空把1压栈。栈内[1(74)]i2温度75栈顶是174751出栈ans[1]2-11。栈空把2压栈。栈内[2(75)]i3温度71栈顶是27571没有形成“大于”所以2不动把3压栈。栈内[2(75), 3(71)]i4温度69栈顶是37169不满足出栈条件把4压栈。栈内[2(75), 3(71), 4(69)]i5温度72此时栈顶是469724出栈ans[4]5-41。接着栈顶是371723出栈ans[3]5-32。再接着栈顶是27572停止。把5压栈。栈内[2(75), 5(72)]i6温度76栈顶是572765出栈ans[5]6-51。栈顶是275762出栈ans[2]6-24。栈空把6压栈。栈内[6(76)]i7温度73栈顶是67673不满足出栈条件把7压栈。栈内[6(76), 7(73)]遍历结束栈里还剩下6和7没有出栈说明它们右侧没有更高温度了ans[6]和ans[7]保持初始值0。最终答案是[1, 1, 4, 2, 1, 1, 0, 0]。这个手推过程中你有没有发现一个关键现象每个元素最多入栈一次、出栈一次所以总操作是2n级别时间复杂度严格O(n)。单调栈“用空间换时间”的优势就在这里体现出来了。3.2 Python版本对照如果平时你用Python刷题下面这份写法更简洁逻辑完全一致def dailyTemperatures(temperatures): n len(temperatures) ans [0] * n stack [] for i in range(n): while stack and temperatures[i] temperatures[stack[-1]]: idx stack.pop() ans[idx] i - idx stack.append(i) return ansPython这边有一个小细节list的append和pop就是栈的push和pop操作时间复杂度都是O(1)不需要额外引入模块。用stack[-1]来取栈顶元素比用stack[len(stack)-1]更简练。3.3 反向遍历解法换个方向其实更舒服正向遍历是“来一个新元素找它之前等待结算的人”。反向遍历的思路则是从右往左走维护一个从栈底到栈顶递增的栈栈里存的是“右侧已经见过的、温度更高的日子的下标”。每到一个位置不断弹出栈顶比当前温度低的下标最终剩下的栈顶如果存在就是“右侧第一个更高温度”的日子。vectorint dailyTemperatures(vectorint temperatures) { int n temperatures.size(); vectorint ans(n, 0); stackint st; for (int i n - 1; i 0; --i) { while (!st.empty() temperatures[i] temperatures[st.top()]) { st.pop(); } if (!st.empty()) { ans[i] st.top() - i; } st.push(i); } return ans; }注意这里出栈的条件是temperatures[i] temperatures[st.top()]意思是“把右边不比当前温度高的全部丢掉”因为有了当前这个更高的温度右边那些更低的温度对于更左边的日子来说已经没有参考价值了。而且特别注意这里是大于等于等于也被弹出去因为等于也不能算“更高”。反向遍历的好处是什么代码更贴合“第一个更大元素”的语义因为栈顶天然只剩下右侧更高的下标。但它也有一个隐蔽风险很多人在写反向遍历的时候容易把出栈条件写成大于号导致碰到相等温度时栈没清干净答案不正确。所以两种遍历方式我建议你至少把正向写法吃透反向写法作为检验思维是否真正掌握的练习。3.4 边界情况逐一过一遍写算法题边界情况永远是最容易出错的环节。“每日温度”常见的边界情况包括数组长度为1比如[30]。此时没有“右侧”直接返回[0]。全部元素都相等比如[50,50,50]。由于要满足严格大于没有任何一个位置能等到更高温度结果全是[0,0,0]。全部单调递增比如[30,40,50,60]。每个位置都等一天就遇到更高温度结果全是[1,1,1,0]。全部单调递减比如[60,50,40,30]。没有任何位置能等到更高温度但每个元素都在栈里走了一遭最后全留在栈里没被弹出。编写完代码我建议你在脑子里对这几个极端场景各走一遍比盲写一百行测试数据都有用。4. 单调栈模板提炼与题型延伸4.1 从每日温度里抽出一个万能模板练完这道题我的经验是你不该只记住这道题的代码而应该把单调栈的处理框架抽出来当作固定套路来记忆。我在自己笔记里是这么写的遍历数组栈里维护“尚未找到答案”的候选下标每来一个新元素把栈内所有“被新元素解开答案”的元素弹出并结算弹完之后新元素下标入栈等待未来处理循环结束后栈内剩余元素一律没有更优答案有了这个框架遇到任何“下一个更大/更小元素”“左右第一个比它大/小的位置”类题目都可以直接套用它再根据题目语义决定栈的单调方向、比较符号、结算方式。4.2 几道经典变体如何复用这个模板第一道变体是“下一个更大元素”系列。它给你两个数组本质上是同一套单调栈逻辑只是多了一个哈希表映射的过程。你先对第二个数组做一次正向单调栈求出每个元素右边第一个更大的值再把结果存到哈希表里最后遍历第一个数组取值即可。第二道变体是“柱状图中最大的矩形”。这道题表面上和温度毫无关系但思路恰恰也是单调栈只是维护的方向相反要找左右两侧第一个更矮的柱子栈内从底到顶保持递增。结算面积时高度由弹出元素给定宽度由左右边界决定。如果你把“每日温度”彻底吃透了再看这道题会发现很多思路都是相通的。第三道变体是“接雨水”。接雨水要找到每个位置左右两侧的最高边界经典解法是用双指针但也可以用单调栈来算。栈底到栈顶递减遇到比栈顶高的弹出栈顶并按宽度和高度差来累加水量。逻辑略绕但核心骨架仍然不变。我提这些变体不是让你现在就去把它们全刷完而是告诉你花在“每日温度”上的时间不需要多但一定要把它背后的模板想透。它会成为你做单调栈类题目的思考起点。4.3 变形时最容易跑偏的三个关键差异变体题目虽然都是单调栈但有三处容易跑偏的地方。第一个是“大于”和“大于等于”的区别。“每日温度”要求严格更高所以正向遍历用大于号弹出如果题目允许相等也算那就要把符号改成大于等于漏掉等于号会导致答案错误。第二个是“找更大”还是“找更小”的方向。这个决定栈内的单调方向。找“下一个更大”基本是栈内递减找“下一个更小”基本是栈内递增。搞反这个栈顶的比较逻辑全乱。第三个是结算内容的差异。“每日温度”结算的是距离所以出栈后算两个下标之差“下一个更大元素”结算的是值本身“柱状图最大矩形”结算的是面积。这说明单调栈是骨架结算公式是灵魂两者需要一起搭配使用。4.4 复杂度分析的严谨推导很多人背过“单调栈时间复杂度O(n)”但不知道它为什么是O(n)。这个一定要能自己推出来。每个下标只会被push入栈一次。它一旦被pop出来就说明已经找到了答案之后不会再入栈。所以对于长度为n的数组push操作总数等于npop操作总数也小于等于n。while循环整体执行的次数不超过入栈总次数也就是O(n)级别。再加上外层循环n次总复杂度仍然O(n)。空间复杂度方面栈最多存n个元素所以是O(n)。这套推导逻辑在面试手写复杂度分析的时候直接说“每个元素入栈出栈最多一次所以均摊O(n)”就够了。说“均摊”是因为while循环看起来可能执行很多次但整体加总不超过n这种说法体现了复杂度分析的专业程度。5. 常见问题与排查技巧实录5.1 我实际调试中遇到的三个典型错误第一个错误是把下标和温度混着用。我在写代码时有一次不小心在比较温度的地方写成了i st.top()一眼看过去好像很合理但它其实是在比较下标比较的完全不是温度。这个问题在数据量小、巧合匹配的情况下很难发现直到我拿一组顺序比较特殊的数据测试才暴露出问题。解决方法是严格明确凡是取温度值必须写temperatures[st.top()]凡是取下标直接操作st.top()或i不要混。第二个错误是忘了处理栈里剩余元素。我早期写正向解法从数组开头遍历完就以为大功告成根本没考虑栈里还剩没弹出的元素。结果栈底那些“永远等不到更高温度”的下标ans位置一直保持0表面上看好像也没错。但有一次我把初始ans直接初始化为-1输出就乱了。严格来说栈里剩余元素其实不需要特殊处理因为它们的答案就是默认值0。第三个错误是把比较符号写成。在正向遍历里如果用弹出两个温度相等也会触发结算。但题意要求严格更高等于不能算。一旦出现连续相同温度结果就会全错。这个坑我栽过两次现在每次写完单调栈都会专门检查比较符号。5.2 用特殊输入序列做自测我给自己定了一套自测输入每次写完单调栈必跑[1, 2, 3, 4, 5]递增序列结果必须是[1,1,1,1,0][5, 4, 3, 2, 1]递减序列结果必须是[0,0,0,0,0][1, 1, 1, 1]全相等序列结果必须是[0,0,0,0][30]单元素结果必须是[0][73, 74, 75, 71, 69, 72, 76, 73]标准测试必须是[1,1,4,2,1,1,0,0]只要这些输入全部通过基本可以确认代码没有大问题。尤其是全相等和单元素这两个容易踩坑的输入很多人都会忽略。5.3 排查逻辑时的三个步骤如果你发现自己写的单调栈代码在某组数据上错了我建议按顺序排查第一步用笔手动推演一遍小规模输入。推演的时候把栈的状态一行一行列出来就像我在前面用的手推方式。只要推演过程中发现某一步的栈状态和你预期不一致问题定位就完成了。第二步给代码加临时调试输出。在for循环里打印i、当前温度、栈内所有元素、弹出下标、结算值。这样能看到真实运行和手推的差异在哪。第三步把题目条件重新逐字读一遍。很多问题不是出在算法上而是出在对题意的理解有偏差。比如“每天的温度”其实是“非负整数”但温度数值本身不重要重要的是大小的相对关系。问题症状可能原因解决办法全相等数组结果不为0比较符号写成了改成严格大于递增数组结果全为0栈内剩余元素结算逻辑写错初始化为0不做额外处理答案整体偏移一天距离计算少了1用下标相减检查是否多减1某些位置结果错乱栈内下标与温度混用统一用temperatures[st.top()]取温度6. 个人实操心得与学习建议自己刷完这道题之后我最大的感受是单调栈的核心不在“栈”这个数据结构本身而在于“延迟结算”这四个字。温度低的那些日子明明当时没有答案但你不急着给它填结果而是把它放进栈里存着等到答案出现的那一天再一次性算清楚。这和大脑处理复杂问题的思路很像——不必要的事先不处理等条件成熟了再集中处理。练习单调栈我有三个经验可以分享。第一个经验是先别急着看题解先自己尝试用暴力法写一遍。暴力法虽然超时但它会逼你认真分析“每个位置到底在找什么”。一旦你发现暴力法里大量重复扫描了已经访问过的元素你就离单调栈的想法不远了。这一步是建立直觉的关键。第二个经验是手推栈状态一定要推到三次以上。“每日温度”的代码即便背下来如果不理解栈里那个“从底到顶递减”的性质是怎么维持的题目换个马甲你就认不出来了。我逼自己把标准测试数据从头到尾推了五遍直到闭着眼能说出来每一步的栈内容才开始做后面的变体题。第三个经验是做变体题时时刻提醒自己“模板相同结算不同”。看到新题先确认三个问题找更大还是更小栈内递增还是递减结算的是距离、值还是面积这三个问题确认完代码框架立即可套。如果你现在刚开始接触单调栈不要指望一次就能完全消化。今天先把正解法会写、会推导明天再试反向解法等你能独立把“柱状图中最大的矩形”做出来的时候单调栈才真正成为你自己的工具。这道题我从超时写超时到完全吃透大概花了两三天。中间一度很想放弃但后来发现单调栈这种“延迟结算”的思路其实每天都在生活里发生。比如你买了一堆东西放在购物车里等到打折的时候再一起结算这就是“延迟结算”。理解了这一层代码里的栈也就没那么吓人了。希望这篇文章能帮你把这道题从“背过”变成“想通”。