我刚开始刷单调栈这个专题的时候也被“每日温度”这道题卡过一阵。LeetCode 739这个题号在算法圈里几乎是“必刷清单”里的常客题目本身看起来平平无奇——给你一组每日温度让你算每个位置要等几天才有更高的温度。但就是这道easy难度的题背后藏着一个非常核心的数据结构思想单调栈。不管是后面的接雨水、柱状图中最大的矩形还是股票价格跨度全都是从这道题的思路上长出来的。这篇文章我会把LeetCode 739每日温度完整拆开从暴力解法一步一步优化到单调栈再把两个方向的遍历写法都给你讲透连边界条件、代码bug高发点、相似题型的识别方法一起聊清楚。不管你是在准备面试、刷hot 100还是单纯想把“单调栈”这个概念彻底搞懂这篇都值得你花十分钟认真读完。1. 题目解读与核心思路拆解1.1 题目到底在问什么先看原题描述给你一个整数数组temperatures表示每天的温度返回一个数组answer其中answer[i]是指对于第i天下一个更高温度出现在几天后。如果气温在这之后都不会升高请在该位置用0来代替。举个具体的例子。输入是temperatures [73, 74, 75, 71, 69, 72, 76, 73]输出应该是[1, 1, 4, 2, 1, 1, 0, 0]逐天拆解一下第 0 天温度 73第 1 天温度 74只隔 1 天就有更高温度所以answer[0] 1第 1 天温度 74第 2 天温度 75同样只隔 1 天所以answer[1] 1第 2 天温度 75需要等到第 6 天的 76相隔 4 天所以answer[2] 4第 3 天温度 71第 4 天温度 69都不如第 5 天的 72 高等 2 天所以answer[3] 2第 6 天温度 76 和 第 7 天温度 73 之后都没有更高温度了所以都是0有一点容易被忽略题里说的“下一个更高温度”是严格大于等于不算。比如温度从 75 到 75你要找的是大于 75 的不是大于等于。这个细节在写单调栈的弹出条件时是一个决定性的分支点后面我会专门说。1.2 为什么暴力解法不是终点先别急着上单调栈我们看看暴力解法能不能写。对每个位置i往后遍历j找到第一个temperatures[j] temperatures[i]记录距离。代码非常短def dailyTemperatures(temperatures): n len(temperatures) ans [0] * n for i in range(n): for j in range(i 1, n): if temperatures[j] temperatures[i]: ans[i] j - i break return ans时间复杂度是 O(n²)。对于题目给的数据范围——温度数组最长能到 10⁵——O(n²) 就是 10⁹ 到 10¹⁰ 级别的操作必然超时。但暴力解有一个价值它是“语义最直白”的写法能帮你验证自己对题意的理解是否正确。我刷题有个习惯拿到题先想暴力确认没问题之后再思考优化手段。这样即使后面单调栈写挂了手里也有一个“标准答案”可以对比调试。1.3 单调栈这个数据结构的直觉那优化点在哪暴力解法慢是因为每次找“下一个更高温度”都是自建一个循环往前扫前面的扫描结果完全没用上。但实际上这些信息是可以通过栈结构维护的。单调栈是一种“栈内元素单调递增或单调递减”的栈。在每日温度这道题里我们需要的是“右边第一个比我大的元素”所以栈内温度应当是单调递减的从栈底到栈顶。为什么是递减因为一旦遇到一个比栈顶元素更大的温度这个温度就是栈顶元素等待的“下一个更高温度”此时栈顶元素的任务完成可以弹出新元素从栈顶进入继续维持单调性。我用生活里的排队来打比方想象有很多人按顺序排队每个人都想知道“什么时候会有一个比我高的人站到我前面”。如果队列中后面的人越来越矮那么前面的人就只能一直等下去一旦出现一个比队伍末尾的人更高的新来者队伍末尾那批矮个子就可以结算答案然后离队。这个离队动作在代码里就是pop()。理解了这一点单调栈的代码逻辑就顺理成章了。2. 从暴力到单调栈三种解法逐层递进2.1 先跑通再优化暴力写法的心得暴力写法虽然慢但中间的坑不算少。我印象最深的是“break 放在哪里”。如果你不小心把break放在if外面那么每个i都会被j遍历完后取最后一个j计算距离答案就完全错了。这道题本身是 easy写对暴力不难但刷题时保持“先确认基准答案正确”的习惯很重要。另一个值得注意的细节是数组边界的处理。如果temperatures长度是 1那么答案只能是[0]。暴力解法里外层循环执行一次内层循环不执行自然得到[0]但这种边界在单调栈里也需要手动确认。2.2 从右往左遍历 单调栈标准解法第一种高效写法是从右往左遍历。思路是维护一个栈栈内存放数组下标并且保证从栈底到栈顶对应的温度是单调递减的。反向遍历时对于当前下标i我需要找到“i 右侧第一个温度高于当前位置”的下标。栈里存的都是已经遍历过的右侧元素如果栈顶的温度不比当前高那它对当前元素没有意义——它不可能是答案而且它还会挡住后面更远的更高温度吗其实不会因为如果栈顶温度不够高且它在当前位置的右边那么即使栈底有更高的温度计算距离时也应该用更近的那个。所以直接把不够高的元素全部弹出就行。这里有个容易混淆的点弹出条件应该是“小于等于当前温度”还是“小于当前温度”由于题目找的是“严格更高”如果栈顶温度和当前温度相等它也不是答案同样需要弹出。所以从右往左写法的弹出条件是temperatures[stack.peek()] temperatures[i]。代码如下class Solution { public int[] dailyTemperatures(int[] temperatures) { int n temperatures.length; int[] ans new int[n]; DequeInteger stack new ArrayDeque(); for (int i n - 1; i 0; i--) { while (!stack.isEmpty() temperatures[stack.peek()] temperatures[i]) { stack.pop(); } ans[i] stack.isEmpty() ? 0 : stack.peek() - i; stack.push(i); } return ans; } }2.3 从左往右遍历 单调栈反直觉但同样优雅第二种常见写法是从左往右遍历维护一个栈栈内存放“还没有找到答案的下标”。从左往右看当遍历到i时如果栈顶温度小于当前温度说明栈顶元素遇到了它的“下一个更高温度”于是弹出并结算答案ans[stack.pop()] i - 栈顶下标。这里弹出条件就变成了严格小于temperatures[stack.peek()] temperatures[i]。为什么等于的时候不弹出因为当前温度并不是“严格更高”栈顶元素还要继续等待后面更大的温度。如果此处把相等的也弹出去那栈顶元素就会被错误地结算成“与当前温度的距离”但题目要求更高温度等值的温度当然不算。这是两个方向写法最大的区别也是面试官最喜欢追问的细节。from typing import List class Solution: def dailyTemperatures(self, temperatures: List[int]) - List[int]: n len(temperatures) ans [0] * n stack [] for i in range(n): while stack and temperatures[stack[-1]] temperatures[i]: j stack.pop() ans[j] i - j stack.append(i) return ans从左往右写法的好处在于它很符合“从左到右扫描”的直觉你不需要预先知道右侧信息只需要把“悬而未决”的下标存在栈里等答案出现时再结算。这种做法其实更接近日常业务里“先记着后面再来补”的处理方式。2.4 两种遍历方向与复杂度对比维度从右往左从左往右栈的含义右侧已经遍历过的下标按温度递减排列左侧还没找到答案的下标弹出条件栈顶气温 当前气温栈顶气温 当前气温结算时机遍历到当前位置时直接算答案遇到更高温度时结算栈顶元素的答案空间复杂度O(n)O(n)时间复杂度O(n)O(n)两个方向的时间复杂度都是 O(n)空间复杂度都是 O(n)。从代码简洁度来看从右往左的写法答案数组的赋值逻辑更直接从左往右的写法则胜在“结算”的动作和人类思考过程一致。我个人建议两种都写一遍对单调栈的理解会明显上一个台阶。为什么单调栈的时间复杂度是 O(n)因为每个下标最多入栈一次、出栈一次while 循环里所有 pop 的总次数不会超过 n。虽然代码里有一个内层 while但均摊下来还是线性时间。这一点在面试里最好能主动讲出来很加分。3. 从零手写 AC 代码多语言实现与边界细节3.1 Java 实现与 Deque 使用技巧Java 里写栈很多人会条件反射用Stack类。但在 LeetCode 上我推荐用ArrayDeque因为它底层是数组实现方法开销更小性能更好而且没有Stack类继承Vector带来的同步锁开销。刷题场景下Stack的push/pop/peek虽然也能用但社区普遍认为ArrayDeque更合适。import java.util.ArrayDeque; import java.util.Deque; class Solution { public int[] dailyTemperatures(int[] temperatures) { int n temperatures.length; int[] ans new int[n]; DequeInteger stack new ArrayDeque(); for (int i n - 1; i 0; i--) { while (!stack.isEmpty() temperatures[stack.peek()] temperatures[i]) { stack.pop(); } ans[i] stack.isEmpty() ? 0 : stack.peek() - i; stack.push(i); } return ans; } }几个细节说一下。stack.peek()在 Java 的Deque接口里返回栈顶元素但不删除空栈时调用会抛异常所以必须先用isEmpty()判断。这一点很多新手容易踩坑。另外ArrayDeque不允许 null 元素但这道题栈里只存整数下标所以没问题。3.2 Python 实现与 typing 注解Python 的写法在 LeetCode 上同样非常流畅直接用列表作为栈即可。stack[-1]取栈顶元素stack.append(i)入栈stack.pop()出栈底层是动态数组复杂度依然是摊销 O(1)。from typing import List class Solution: def dailyTemperatures(self, temperatures: List[int]) - List[int]: n len(temperatures) ans [0] * n stack [] for i in range(n): while stack and temperatures[stack[-1]] temperatures[i]: j stack.pop() ans[j] i - j stack.append(i) return ansPython 里要注意的一点是while stack and这个条件的顺序不能写反。如果写成while temperatures[stack[-1]] temperatures[i] and stack当stack为空时stack[-1]会直接抛IndexError。虽然这是基础常识但刷题时手速一快就容易犯。我的习惯是永远把stack的非空判断放在前面。3.3 原地复用数组减少空间的小技巧如果你追求极致可以不用额外开ans数组直接把结果写回temperatures本身。因为原始温度数组在结算完成之后就没有其他用途了覆盖它不会丢失信息。这样空间复杂度从 O(n) 降到 O(1)除了栈本身。不过 LeetCode 的判题并不限制额外数组这个优化更多是为了面试时展示细节。from typing import List class Solution: def dailyTemperatures(self, temperatures: List[int]) - List[int]: n len(temperatures) stack [] for i in range(n): while stack and temperatures[stack[-1]] temperatures[i]: j stack.pop() temperatures[j] i - j stack.append(i) while stack: temperatures[stack.pop()] 0 return temperatures这里要注意最后栈里剩下的元素都是没有找到更高温度的下标需要把它们统一赋值为 0。如果忘了这一步答案数组里会残留原来的温度值。这个 bug 特别隐蔽我第一次写的时候就漏了导致结果里出现了一堆原始温度排查了半天才发现是初始化问题。3.4 边界条件处理清单边界条件在刷题里是老生常谈但每日温度这道题的边界其实不多整理下来就是三件事数组长度为 0返回空数组。大多数语言里直接new int[0]或[]即可。数组长度为 1返回[0]因为后面没有元素了。温度持续递增、持续递减、全部相等这三类数据可以用来快速验证代码是否正确。我用一个最长递减序列验证过比如[30, 29, 28, 27]答案应该全是 0。如果用从左往右的写法所有下标都会被压入栈中直到遍历结束都没有弹出最后栈里剩下全部元素需要统一赋 0。这里正好能看出为什么从左往右写法里“最后清栈”是必要的。4. 常见问题与排查技巧实录4.1 为什么栈里存下标而不是直接存温度这是新手最容易疑惑的问题。我们的目标是计算“距离”也就是下标的差值。如果栈里只存温度值那么当找到更高温度时你无法得知两个温度相隔几天。虽然你可以额外用哈希表把温度映射回下标但那样做空间更大、逻辑更绕完全没有必要。栈内存下标是一种“用位置换信息”的经典思路后面很多单调栈题都是这么处理的。4.2 等值温度到底怎么处理再把这个容易错的地方单独拎出来放大讲一遍。题目要的是“下一个更高温度”所以等值不算。从右往左写法弹出条件用因为等于当前温度的右侧元素对当前元素来说不是答案且它还会阻挡我们直接看到更远处真正更高的温度所以一并丢掉。从左往右写法弹出条件用因为等于栈顶温度时当前温度不是栈顶元素的“更高温度”不能结算。如果两个方向的弹出条件对调答案就会出错。比如输入[73, 74, 74, 75]正确输出是[1, 2, 1, 0]。你可以分别用错误的弹出条件跑一遍会发现第二个 74 的答案被算成了 1但实际上是 2。4.3 栈里剩下的元素为什么一定是 0从左往右遍历结束后栈里剩下的下标表示这些元素之后没有出现过比它们更高的温度。为什么因为如果有更高的温度它们早就被弹出结算了。能留在栈里说明后面没有“更强”的元素出现。所以统一赋 0 是正确且必要的。从右往左遍历时由于每个位置都在扫描时直接计算答案如果栈为空说明右侧没有更高温度直接赋 0。不存在“最后补 0”的步骤这也是很多人觉得从右往左写法更干净的原因之一。4.4 单调栈时间复杂度的均摊分析面试时经常被追问“内层不是还有 while 吗为什么是 O(n)”你需要讲清楚每个元素只入栈一次、出栈一次所以 while 循环整体执行的次数不超过 n。虽然单次来看 while 可能连续弹出很多元素但那些元素弹出之后就不会再回来了均摊到整个过程还是 O(n)。这本质上是“每个元素被处理常数次”的均摊思想和动态数组扩容的均摊分析是一个套路。我建议你在白板上画一个递减序列和一个递增序列手动模拟一下栈的变化过程。递减序列里每来一个新元素都会弹出多个栈顶元素你会直观看到总弹出次数是有限的而不是每次循环都弹出 O(n) 个。4.5 提交出错后的排查顺序如果你写完代码提交 WAWrong Answer我一般按这个顺序排查先跑示例用例确认输出是否符合预期。跑[1, 1, 1, 1]确认等值温度是否被正确处理。跑[1, 2, 3, 4]和[4, 3, 2, 1]确认递增和递减序列是否合理。检查栈内存的是不是下标而不是温度。检查遍历方向是否和弹出条件配套。这套流程用下来十有八九能在两分钟之内定位问题。5. 从一道题延伸出一类题单调栈的模型与应用5.1 题型识别下一更大元素系列LeetCode 739每日温度本质上是“下一个更大元素”问题的一个变种。同系列的题目还包括LeetCode 496下一个更大元素 I两个数组单调栈 哈希表LeetCode 503下一个更大元素 II循环数组把数组翻倍模拟环LeetCode 84柱状图中最大的矩形单调栈 哨兵LeetCode 42接雨水虽然解法很多但单调栈也完全可解这些题的核心都是在数组中找到每个元素左边或右边第一个比它大或小的元素并计算距离、面积或直接取值。一旦你在每日温度里建立了单调栈存下标、按单调性弹出、遇到更大元素结算的思维模型上面这些题都可以顺势拿下来。5.2 实际业务场景中的映射单调栈不只是面试题。举几个实际场景股票交易场景中给定一支股票每天的价格想知道每个交易日之后第一次涨价要等多少天这就是每日温度的翻版。服务器日志场景中统计每个请求之后第一个响应时间更长的请求本质上也是“下一个更大元素”的变体。天气预报系统中如果你要做“未来几天气温上升提示”原始数据结构就和这个题一模一样。所以别看它是 easy 题背后的模型迁移能力非常强。所谓“算法思维”很多就是从这种小问题里训练出来的。5.3 多语言实现对比小结单调栈代码本身不长但不同语言写起来各有优劣。Java 需要写Deque的完整类型声明略显啰嗦但运行性能稳定Python 代码最简洁适合快速验证思路C 用vectorint stk作为栈极其方便我个人刷题时最常用 C 的 vector 模拟栈连stack容器都不用引入。不论用什么语言写完之后都建议自己手动跑一遍小用例把栈的变化过程写在纸上。这一步看起来笨但能让你真正理解为什么元素会被弹出、为什么答案等于下标之差。5.4 相关热词延伸热门100题与周赛趋势现在 LeetCode 热门 100 题里单调栈相关题目数量不少每日温度、接雨水、柱状图中最大的矩形基本是必刷常客。近期周赛里也经常出现“下一个更大元素”的变形题有时候套一层 DP、有时候套一个循环数组或二维数组但内核实测下来都没有跳出单调栈这套模型。所以我的建议是与其在周赛里被新题突击不如先把每日温度彻底吃透把单调栈的各种写法都练到闭眼能写这样遇到新题时你至少有个稳定的思维起点。6. 实操心法与刷题建议6.1 刷题时建议坚持“三遍法”第一遍先做出来什么方法都行暴力也可以。第二遍追求最优解把单调栈写出来并且要能解释清楚每一步的为什么。第三遍隔几天再写一遍看看能不能不假思索地写出来。我身边很多朋友第三遍才发现自己“以为懂了但其实没懂”因为细节太多光靠记忆根本撑不了几天。6.2 模拟展示我自己在本地调试时用的用例调试时我不建议只跑题目给的例子因为样例往往设计得过于友好。我常用下面这组用例[34, 80, 80, 34, 34, 80, 34, 34]正确答案是[1, 0, 0, 2, 1, 0, 0, 0]这个用例里有连续相同温度、从高温到低温、从低温到高温的跳变基本上把边界条件全照顾到了。如果你用这组数据测试从左往右写法和从右往左写法都能跑通那这道题大概率是没问题了。6.3 给刚开始刷题的人一个定心丸如果你第一次接触单调栈觉得晦涩这很正常。单调栈比普通栈抽象因为它多了一层“栈内元素有序”的约束做题时需要额外思考“什么时候入栈、什么时候出栈、出栈时结算什么信息”这三件事。但好消息是你只需要吃透三五道题就能把这种思维固定下来。每日温度就是最好的入门题没有之一。我个人是把这道题放在“单调栈专题”的第一道来刷的后面再接柱状图中最大的矩形和接雨水。实测下来这种顺序的曲线最自然。反之如果一上来就碰接雨水很容易因为思维跳跃过大而受挫。6.4 关于本地调试环境的一点经验LeetCode 网页编辑器虽然方便但我遇到复杂 debug 时还是会复制到本地 IDE 里加上一些辅助输出。比如可以在遍历过程中打印当前下标、当前栈内容、弹出的下标和答案值。这样你能亲眼看到“什么时候结算结算成多少”比单步调试更直观。这招在写单调栈题的时候特别管用。这里分享一个我自己的小工具写法如果你输入的是 Java 的int[]可以直接在本地 main 方法里写一个循环打印Python 更简单在关键位置插print即可。但记得提交前把打印删掉否则输出不匹配会导致 WA。7. 总结是多余的经验和细节才是重点刷题这么多年我最大的体会是算法题的价值不在于你 AC 了多少道而在于你有没有把一道题的细节吃透。LeetCode 739每日温度这道题表面上是 easy但如果你能把两个方向的单调栈写法、等值温度的处理、栈内存下标的理由、时间复杂度均摊分析都讲清楚那你的水平其实已经超过了很多只刷题不思考的人。写这篇博客的时候我又把两种写法各手写了一遍确认代码没有 bug。落地到你的实战中我建议你第一遍用从右往左写法 AC第二遍尝试从左往右写法第三遍挑战一下原地复用的优化写法。三遍下来你基本可以做到在面试里流畅地讲出思路和细节。最后再分享一个小技巧刷完每日温度之后马上去做 LeetCode 503“下一个更大元素 II”那道题只是把数组变成循环数组解法核心完全一致。这种“趁热打铁”的连续刷法比分散着刷十几道不同专题的题效果好得多。是算法学习没有太多捷径但把单点打穿的笨功夫恰恰是最快的路。