★ FEATURED ARTICLE LeetCode 739题《每日温度》大概是很多人的第一道单调栈启蒙题。题目本身不长读一遍就懂——给一个每天温度的数组返回一个新的数组每个位置表示要等多少天才会出现更高的温度等不到就填0。就这么一句话的题暴力解两分钟就能写完可一旦数据量上来暴力解立刻原形毕露。这篇文章我不打算只贴代码我想把整个思考过程拆开讲为什么暴力解不行单调栈到底在做什么栈里为什么存的是下标不是温度以及真正把这个题吃透之后你能顺手拿下的一串变体题。1. 先说清楚题目在考什么1.1 把题目翻译成人话题目给的是一个整数数组长度最长能到10的5次方每个元素代表当天温度。要你返回一个等长的数组其中第i个位置的数字含义是从第i天开始要等多少天才会遇到第一个温度比当天高的日子。如果后面再也没有更高的温度那这个位置就是0。拿题目给的标准示例来拆[73, 74, 75, 71, 69, 72, 76, 73]期望输出是[1, 1, 4, 2, 1, 1, 0, 0]。我挨个解释一遍你就彻底明白了。第0天73度第1天74度所以只等1天输出1。第1天74度第2天75度也是1。第2天75度要一直等到第6天的76度才遇到更高温度中间隔了4天输出4。第3天71度第5天72度就是更高温度等了2天。第4天69度第5天72度等了1天。第5天72度第6天76度等了1天。第6天76度后面第7天只有73度再往后没了输出0。第7天73度是最后一天后面没有数据输出0。这里有个特别容易被忽略的细节题目说的是更高温度不是大于等于。也就是说如果后面某天温度和当天一样哪怕相等也不算是找到了更高温度。比如温度序列是[70, 70, 71]第0天70度要等到第2天71度答案是2不是1。这个严格大于的语义直接决定了后面单调栈弹出条件怎么写很多新手第一次写错就是错在这里。从问题的本质看这题就是在找每个元素右侧第一个比它大的元素并且要记录两者之间的距离。这种抽象模式在计算机里叫Next Greater Element下一个更大元素。温度只是题目给你包装出来的场景剥掉这层场景你要解决的是一个非常纯粹的数组遍历与比较问题。理解到这一层比记住答案重要得多。1.2 数据规模决定了你不能用暴力解我刚拿到这题的时候第一反应也是暴力循环对每个位置i从i1往后遍历找到第一个temperatures[j] temperatures[i]就停下来记录j - i找不到就填0。伪代码长这样for (int i 0; i n; i) { for (int j i 1; j n; j) { if (temperatures[j] temperatures[i]) { res[i] j - i; break; } } }代码逻辑完全正确样例也肯定能过。但你看一下数据范围n最大是10的5次方。最坏情况下比如温度数组是一个严格递减的序列[100, 99, 98, ... , 1]那么第0天要往后面扫n-1次才能确认后面没有更高温度第1天要扫n-2次累加起来就是大约n的平方再除以2。10的5次方平方一下是多少10的10次方次操作。现代CPU一秒大概能执行几亿次简单操作10的10次方这个量级跑起来基本就是几十秒起步而在线评测系统给你的时间限制通常是1到2秒。所以暴力解不是不够优雅的问题是压根跑不完的问题。我见过很多同学在面试里一边写暴力解一边说我能想到优化但真实面试中你写完暴力解之后一定要立刻分析复杂度自己主动说出O(n^2)在10的5次方数据下不可行。能主动说出这一步比被面试官追问出来要加分得多。暴力解存在的意义不是让你提交而是作为基线帮你验证优化方案的正确性。1.3 这类场景包装背后的算法模式温度只是个例子。实际上找下一个更大元素这个模式在真实场景里出现频率相当高。比如股票K线里你想知道当前价格之后的几天内什么时候能涨回成本价比如传感器数据流里你想知道每个读数之后多久会出现一个超过阈值的值再比如排队场景里你想知道站在你前面的队伍里什么时候会出现一个比你更高的人挡住你的视线。这些问题的抽象结构完全一样给定一个序列对于每个位置找到右侧第一个满足某种比较关系大于、小于的元素并计算距离。我在实际带人刷题的过程中发现很多人不是不会写代码而是不会脱壳。题目一包装成气象数据、股票数据、游戏分数就慌了。这里给一个非常实用的建议读题之后不要盯着场景想而是把场景词汇划掉换成抽象词汇。比如温度换成数值几天后换成下标差更高换成大于。一替换题目的本质就浮现出来了。每日温度脱壳之后就是对数组每个位置求右边第一个大于当前值的元素下标与当前位置的差。你把这个抽象问题写在白纸上再看单调栈思路会顺很多。2. 单调栈一个数据结构如何解决这种问题2.1 核心原理维护一个递减的栈单调栈顾名思义就是栈内元素从栈底到栈顶保持单调性。放在这个题里我们要维护的是一个从栈底到栈顶温度严格递减的栈。为什么是递减因为每遍历到一个新元素它都在尝试终结栈顶元素等待状态——如果新温度比栈顶温度高说明栈顶那个一直没找到答案的元素现在终于找到了它右边第一个比它大的值。这时候栈顶的任务完成应该出栈并且它到新元素下标之间的距离就是答案。我习惯用一个生活类比来理解想象一列人在排队每个人都想知道自己后面第一个比自己高的人离自己多远。队伍从左到右依次处理我们手里没有菜单只能一个个往后看。用单调栈的时候栈里存的是那些还没找到身后更高者的选手。新来一个人如果他的身高比栈顶的人高那么栈顶那个人就可以出栈了因为新来者就是他要找的答案。栈顶处理完之后新的更矮或更矮的人继续入栈等着下一个更高的人出现。这个过程最妙的地方在于每个元素只会被压入栈一次、弹出栈一次。也就是说虽然代码里有一个内层的while循环但总弹出次数不会超过总入栈次数整体操作量是线性的。这就是为什么单调栈能把O(n^2)的暴力解压缩成O(n)。它不是用什么高深魔法而是把之前扫描过的信息用栈保存了下来避免了重复遍历。2.2 关键细节栈里存的是下标而不是温度这是整道题里最容易忽略、但面试官最喜欢追问的地方。新手很容易写成在栈里存温度值存完发现算不出等几天。为什么要存下标因为答案要求的是天数差也就是两个下标之差。如果你只存温度你只知道栈顶温度是75但你不知道它出现在数组的哪个位置也就没法计算j - i这个差值。正确的做法是栈内存下标需要比较温度时用下标从原始数组里取值。比如栈顶是stack.peek()想拿它对应的温度就写temperatures[stack.peek()]。这样既保留了位置信息也能随时取得温度值一举两得。这个细节我在面试模拟中反复强调如果你能把为什么存下标讲清楚说明你理解了下标才是连接数据与答案的桥梁比你默写出完整代码更能体现水平。还有一个更隐蔽的细节栈内温度是严格递减还是允许相等因为题目要求更高温度等于不算数所以当新温度等于栈顶温度时不能弹出栈顶而是要让新下标也入栈。换句话说这里是严格递减相等的温度会共存于栈中。举个例子温度序列[70, 70]第0天入栈第1天和第0天温度相等不弹出第0天直接把第1天入栈最终第0天的答案保持默认0。如果你允许相等弹出就会错误地认为第0天在第1天找到了更高温度输出1答案直接错掉。2.3 正序遍历与逆序遍历两种思路单调栈解决这道题有两种主流写法分别是正序遍历和逆序遍历。正序遍历从左往右的思路是当新元素比栈顶大时栈顶元素熬到头了弹出并结算答案。这种写法符合直觉也是大多数人最先接受的方式。逆序遍历从右往左的思路是倒着遍历数组栈里维护的是已经看过的右边元素中温度递增的一个序列每到一个新位置先把栈里小于等于当前温度的元素全部弹出然后栈顶就是右边第一个比当前温度大的元素的下标直接就可以算答案。两种写法的时间复杂度、空间复杂度完全一样但思考方向不同。逆序写法代码稍短一些因为不需要在弹出时回头修改res而是在入栈前直接读出答案。不过我个人建议新手优先掌握正序版本因为它和下一个更大元素的定义方向一致更不容易把下标关系搞混。等你把正序写熟了再去看逆序版本会发现只是把结算时机从弹出时换成了入栈前。面试中如果被问到能不能换一种遍历方式你能流畅写出逆序版本是一个很不错的加分表现。这里先给出逆序版的伪代码思路具体代码在下一节一起展示初始化一个空栈从i n - 1往左遍历每次先while弹出所有栈顶温度小于等于当前温度的下标然后如果栈不为空res[i] stack.peek() - i最后把i压入栈。3. 代码实现与手把手推演3.1 主角代码Java正序遍历实现直接上能跑的代码我用Java写因为面试里Java和C最常出现逻辑也最规整。class Solution { public int[] dailyTemperatures(int[] temperatures) { int n temperatures.length; int[] res 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(); res[idx] i - idx; } stack.push(i); } // 栈中剩余元素右边没有更高温度res默认0即可 return res; } }我逐行拆解一下关键逻辑。第一DequeInteger stack new ArrayDeque();为什么用ArrayDeque而不是Stack因为旧版Stack类继承自Vector线程安全带来额外开销性能不如ArrayDeque而且在工程实践里ArrayDeque作为栈用更推荐。当然你写LinkedList做栈也没问题但ArrayDeque性能更好。第二最核心的是while循环。每次新来一个温度我就看栈顶只要栈不为空且当前温度比栈顶温度高就说明栈顶元素已经等到了它想要的更高温度。于是弹出栈顶记录答案i - idx。这里特别注意答案赋值是给res[idx]也就是被弹出的那个下标而不是当前下标i。写成res[i] i - idx就大错特错了。接着如果栈顶温度仍然比当前温度低继续弹出直到栈空或栈顶温度不低于当前温度。最后把当前下标i压入栈。3.2 再来看Python和C写法Python版本写起来非常清爽适合在笔试里快速手写def dailyTemperatures(temperatures): n len(temperatures) res [0] * n stack [] for i in range(n): while stack and temperatures[i] temperatures[stack[-1]]: idx stack.pop() res[idx] i - idx stack.append(i) return resC版本需要注意用vectorint模拟栈class Solution { public: vectorint dailyTemperatures(vectorint temperatures) { int n temperatures.size(); vectorint res(n, 0); vectorint stk; for (int i 0; i n; i) { while (!stk.empty() temperatures[i] temperatures[stk.back()]) { int idx stk.back(); stk.pop_back(); res[idx] i - idx; } stk.push_back(i); } return res; } };三种语言的核心逻辑完全一致区别只在于栈的底层API。这里给你一个建议不要贪多面试中选定一门你最熟的语言把正序遍历的写法练到闭着眼能写出来为止。语言换来换去反而容易搞混API。3.3 手推一遍完整样例光看代码还是不够我带你完整推演一遍标准样例。温度数组是[73, 74, 75, 71, 69, 72, 76, 73]我们跟踪每一步的栈内容和结果数组变化。步骤当前下标i当前温度while弹出过程栈内容从底到顶res变化1073栈空跳过[0]无2174弹出下标0[1]res[0] 1 - 0 13275弹出下标1[2]res[1] 2 - 1 14371无弹出71 75[2, 3]无5469无弹出69 71[2, 3, 4]无6572弹出4弹出3[2, 5]res[4] 1res[3] 27676弹出5弹出2[6]res[5] 1res[2] 48773无弹出73 76[6, 7]无推演到这一步栈里还剩下标6和7它们对应的温度76和73右边都没有更高温度了所以保持初始值0最终答案就是[1, 1, 4, 2, 1, 1, 0, 0]。在第6步的时候暂停一下仔细看当前温度72栈从底到顶是[2, 3, 4]对应温度是[75, 71, 69]。72先比栈顶69大弹出下标4res[4] 5 - 4 1说明69在1天后遇到72然后72又比新的栈顶71大弹出下标3res[3] 5 - 3 2说明71在2天后遇到72接着栈顶是下标2对应温度7572不大于75循环停止下标5入栈。你会发现被弹出来的元素都是已经找到答案的留在栈里的都是还没找到的。这个谁弹出谁结算的时机是整个算法的灵魂。3.4 复杂度分析为什么它真的只有O(n)时间上每个元素最多被压入栈一次、弹出栈一次。虽然while循环内部可能连续弹出很多个元素但所有弹出的总次数等于所有元素入栈的总次数也就是n。所以整个算法的总操作次数是O(n)的级别其余的入栈操作也是每个元素一次总时间就是O(n)。空间上栈中最多同时存储n个下标比如温度严格递减的极端情况[100, 99, 98, ...]所有元素都因为没有遇到更高温度而留在栈里空间复杂度就是O(n)。结果数组本身也是O(n)。很多人第一次看到这个解法会怀疑内层明明有个while怎么可能是O(n)这里的关键在于均摊思想。你可以想象每个元素进栈时身上背着一张入场券出栈时消耗这张券。入场券总数是n所以出栈次数最多也是n。就算某一次while循环连弹了100个元素那也是之前100次入栈积累下来的不是额外新增的。均摊到每个元素上就是常数时间。这个均摊分析的思路在后续很多数据结构的复杂度分析里都会用到理解它比背复杂度结论重要得多。4. 实战中踩过的坑、变体与扩展4.1 最容易翻车的三个细节第一个坑等于温度处理错误。前面说过题目要求更高温度相等不算。所以while条件必须是temperatures[i] temperatures[stack.peek()]写成就错了。具体场景[73, 73, 74]第0天和第1天温度相同如果使用第1天到来时会弹出第0天并误以为第0天在第1天找到了更高温度输出[1, ...]正确结果应该是第0天等到第2天的74度输出[2, ...]。第二个坑答案赋值方向写反。res[idx] i - idx不是res[i] idx - i。这里idx是被弹出的元素下标i是当前下标i一定大于idx。如果写成res[i] i - idx就会把答案赋给错误的位置而且idx - i还会算出负数调试起来非常难受。第三个坑空栈调用peek。while循环里必须先用!stack.isEmpty()做短路判断Java和C里短路与能够保证左侧为false时不再执行右侧表达式所以!stack.isEmpty() temperatures[i] temperatures[stack.peek()]是安全的。但如果你把两个条件换顺序写成temperatures[i] temperatures[stack.peek()] !stack.isEmpty()当栈为空时stack.peek()直接抛异常。Python里则是while stack and ...同样注意顺序。4.2 一个冷门但有意思的跳跃解法在面试中如果你能在单调栈之后补充一个跳跃解法会显得你对问题理解更深。这个解法不依赖栈利用已知答案做跳跃思路非常巧妙。先说核心从右往左遍历对于位置i令j i 1如果temperatures[j] temperatures[i]就让j跳到j res[j]的位置——因为res[j]记录了位置j右边第一个比它大的地方。如果res[j] 0说明j右边没有更大的那i右边也肯定没有更大的了直接跳出。代码长这样public int[] dailyTemperatures(int[] temperatures) { int n temperatures.length; int[] res new int[n]; for (int i n - 2; i 0; i--) { int j i 1; while (j n temperatures[j] temperatures[i]) { if (res[j] 0) { j n; break; } j res[j]; } if (j n) { res[i] j - i; } } return res; }这个跳跃解法的平均复杂度接近O(n)最坏情况下某些数据可能退化但实际跑起来表现很好。我推荐你把它当作一个彩蛋来学先掌握单调栈的稳定写法再理解跳跃解法的加速逻辑。面试中时间紧张时优先讲单调栈因为它的复杂度分析是严格可靠的。4.3 吃透一题顺手拿下系列变体每日温度是下一个更大元素的最基础版本。你把它吃透之后下面这些题会变得非常轻松。496. 下一个更大元素 I给两个数组求nums1中每个元素在nums2中对应位置的右边第一个更大元素。思路是先用单调栈预处理nums2得到一个哈希表记录每个数的下一个更大值再遍历nums1查表即可。本质还是找下一个更大元素只是多了一层映射关系。503. 下一个更大元素 II循环数组版本处理方式非常经典把数组拉直成两倍长度遍历2 * n次用i % n取下标。单调栈逻辑和每日温度几乎一模一样只是答案数组存的是元素值而不是距离。901. 股票价格跨度栈内存价格和跨度两个信息实际上是左边第一个更大价格的镜像问题入栈时累积跨度。理解了单调栈谁弹谁结算的逻辑这道题就是一碟小菜。84. 柱状图中最大的矩形这是单调栈里的进阶题需要往左和往右分别找边界本质上还是维护单调栈但结算时机和答案计算方式更复杂。建议你先把每日温度的代码写到滚瓜烂熟再碰这道题。面试回答这类题时我一般按这个节奏来先复述问题并脱壳成找下一个更大元素然后说暴力解是O(n平方)接着提出用单调栈优化到O(n)解释栈里存下标的原因最后补上边界条件的处理。整套讲下来大概三分钟既展示了思考过程又体现了沟通能力。最后再分享一个小技巧刷题不必追求代码一次写对但一定要在纸上手动模拟一遍出栈入栈的过程。我在带新人时经常发现代码能背下来的人并不少但一旦被问到第5步为什么弹出下标3很多人就卡壳了。能用手推清楚每一步的人才算真正把单调栈装进了脑子里。这个习惯比多刷十道题都管用。
阅读完成 · 觉得有帮助？
