LeetCode 739 每日温度：单调栈详解与机考实战

机考刷题这个系列写到第8篇，终于轮到一道让人“一拍大腿”的经典题了：LeetCode 739 每日温度。说它是经典，不是因为它有多难，而是因为它把“单调栈”这个数据结构讲得特别生动——你甚至不需要背模板，跟着题意走一遍，栈的进出逻辑就长在脑子里了。这道题在笔试里出现频率不低，尤其是偏向算法岗的上机笔试，经常作为单调栈的入门题出现；更重要的是，它背后的“下一个更大元素”思想，在后面很多难题里都会反复用到。这篇就把题目拆开细细讲一遍，从暴力解到单调栈，从原理到代码，再附上我在机考和刷题过程中踩过的几个坑，希望能帮到正在准备笔试或面试的朋友。

1. 题目拆解：LeetCode 739 到底在问什么

1.1 先读懂题面，再想解法

题目给你一个整数数组temperatures，表示连续若干天的每日温度。要求返回一个同样长度的数组answer，其中answer[i]表示：从第i天开始，要等几天才能等到一个比当天更高的温度。如果之后没有更高的温度，那这一位就是0。

举个例子：

temperatures = [73, 74, 75, 71, 69, 72, 76, 73] answer = [1, 1, 4, 2, 1, 1, 0, 0]

第 0 天是 73 度，第 1 天就是 74 度，所以等 1 天；第 2 天是 75 度，要等到第 6 天的 76 度，中间隔了 4 天；最后一天之后再也没有更高温度，填 0。

这里最容易被忽略的一个点就是“距离”。题目问的是“几天后”，不是“第几天”，所以答案不是下标，而是下标之差。这个转换直接决定了后续代码怎么写——我们最终要的是j - i，不是j。

1.2 暴力解法很容易想到，但笔试里大概率过不了

拿到题，第一反应肯定是两层循环：对每个i，从i+1开始往后扫，找到第一个大于temperatures[i]的位置j，然后记录j - i。

public int[] dailyTemperatures(int[] temperatures) { int n = temperatures.length; int[] ans = new int[n]; 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; }

这段代码逻辑完全正确，示例也能过。但问题出在复杂度上：最坏情况下，比如数组整体递减[100, 99, 98, ..., 1]，每个i都要往后扫到数组末尾才能确认“没有更高温度”，总共要比较约n(n-1)/2次。LeetCode 这道题的约束是n最大到10^5，也就是最多 100000 天，10^10级别的比较次数，在在线评测系统里跑出来就是妥妥的超时。

所以这道题的核心考点其实不是“能不能模拟题意”，而是“能不能把 O(n^2) 优化到 O(n)”。笔试和面试官真正想看的，就是你知不知道这里该用单调栈。

2. 单调栈思路：把“往后找”变成“往前解答”

2.1 换个视角：让新来的温度去解答等待者

暴力解的问题在于，每个元素都在傻傻地“向后看”，重复扫描了大量区间。你想一下，第 i 天在等一个更高温度，它根本不知道答案在哪；但反过来，当某一天出现了一个更高的温度时，它能立刻解答前面所有“还没等到答案”的日子——只要那些日子的温度比自己低。

这个视角转换，就是单调栈的切入点。

维护一个栈，里面存放“还在等待更高温度”的下标。遍历数组时，每来一个新温度t，就把它和栈顶下标对应的温度比较：

• 如果t大于栈顶温度，说明栈顶这一天终于等到了“第一个更高的温度”，于是弹出栈顶，记录答案当前下标 - 栈顶下标。
• 然后继续比较新的栈顶，因为t可能同时解答好几天的等待。
• 直到栈为空，或者t不大于栈顶温度，再把当前下标压栈，因为当前这一天自己也变成了“等待者”。

整个过程，每个下标最多入栈一次、出栈一次，均摊时间复杂度 O(n)。

2.2 单调栈里到底存什么？为什么不能只存温度

这是很多初学者第一个卡住的地方：栈里应该存下标，而不是温度值。

原因很简单，答案要的是“天数差”，也就是下标差。只存温度值的话，弹出时你根本不知道这个温度是哪一天的，还得再建一张值到下标的映射，纯属给自己添麻烦。直接用下标，既可以通过temperatures[stack.peek()]取出温度做比较，又能在弹出时立刻算出距离，一举两得。

至于栈本身的单调性，细心观察会发现：从栈底到栈顶，温度是递减的。因为新元素入栈前，会把所有比它小的栈顶元素都弹出去，剩下的栈顶是第一个大于等于它的温度。换句话说，栈里维护的是一个“还没被解答、温度依次变低”的序列。这个序列天然就是单调递减的。

这里要先给一个关键提醒：题目要求的是“更高温度”，所以比较时用的是严格大于，也就是temperatures[stack.peek()] < temperatures[i]才弹出。温度相等时不弹出，这一点后面会专门细说，因为它是一个高频错误点。

3. 代码实现：Java 和 Python 的完整写法

3.1 Java 版本与逐行解读

Java 里推荐用ArrayDeque当栈用，而不是Stack类。Stack是遗留类，性能相对较差，而且基于Vector，有同步开销；笔试场景下用ArrayDeque更干净。

public int[] dailyTemperatures(int[] temperatures) { int n = temperatures.length; int[] ans = new int[n]; Deque<Integer> stack = new ArrayDeque<>(); for (int i = 0; i < n; i++) { while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) { int idx = stack.pop(); ans[idx] = i - idx; } stack.push(i); } return ans; }

几个细节值得说一下：

• 结果数组默认值就是 0，所以栈里最终残留的那些“等不到更高温度”的下标，完全不需要额外处理，直接留 0。
• while不能换成if。新温度可能比栈里连续的多个温度都高，比如遇到 76 时，它需要一口气解答 69、71、75 这三天的等待，只用if最多处理栈顶一个，答案就会错。
• 判断条件里的小于号别写反。一旦写成>或者>=，整个栈的逻辑就全乱了。

3.2 Python 版本与语法细节

Python 的写法更简洁，但要注意列表模拟栈时，栈顶是列表末尾元素：

def dailyTemperatures(temperatures): n = len(temperatures) ans = [0] * n stack = [] for i in range(n): while stack and temperatures[stack[-1]] < temperatures[i]: idx = stack.pop() ans[idx] = i - idx stack.append(i) return ans

在 Python 里写这道题，最容易踩的坑是用list的pop(0)来当队列用，那是 O(n) 的操作；但在这里我们只用pop()弹出末尾，均摊下来就是 O(1)。另外注意stack里存的是下标，比较温度时要写temperatures[stack[-1]]，不要误写成stack[-1]本身和温度比。

3.3 完整模拟一次：一趟遍历看清栈的变化

光看代码还是抽象，我用示例数据[73, 74, 75, 71, 69, 72, 76, 73]走一遍全过程，把每一步的栈状态和答案变化列出来：

遍历结束，栈里还剩下标 6 和 7，它们对应的温度分别是 76 和 73，之后再也没有更高温度了，所以答案保持默认值 0。最终结果就是[1, 1, 4, 2, 1, 1, 0, 0]，与题目完全一致。

你会发现一个有意思的现象：栈里的下标对应的温度，从栈底到栈顶始终是递减的。这就是“单调栈”名字的由来。理解了这个单调性，后面看任何单调栈题目的代码都会轻松很多。

4. 边界条件与高频坑点：这些地方最容易翻车

4.1 相等温度到底要不要出栈

很多人在写判断条件时，习惯性地用<=或者>=来处理相等的元素。但在这道题里，这样做会出错。

看一个具体例子：[73, 73, 74]。正确答案是什么？第 0 天是 73，第 1 天也是 73，算不得更高，所以要等到第 2 天的 74，等待天数为 2；第 1 天同样等 1 天。正确答案是[2, 1, 0]。

如果错误地用temperatures[stack.peek()] <= temperatures[i]作为弹出条件，前两个 73 相遇时，第一个 73 会立刻被弹出，ans[0]被写成1，结果就成了[1, 1, 0]。第 0 天明明等了两天，却被错误记录成 1 天，整体答案就是错的。

根源在于“更高温度”天然要求严格大于。两个温度相等时，后面的温度并不能解答前面的等待，所以不能出栈。以后做类似的“下一个更大元素”题目，先确认题目里说的是“大于”还是“大于等于”，这一字之差直接决定代码对错。

4.2 栈里存值不存下标的连锁问题

前面说过要存下标，但我在实际带人刷题时见过太多人第一版写成存温度值。存温度本身并不是完全不能做，但你会立刻发现两个麻烦：

一是计算天数差时需要知道原数组的下标，你不得不额外维护一个“温度值 -> 最近下标”的映射，或者干脆在栈里存一个二元组。这就让代码复杂了很多。二是如果存在重复温度，一个温度值对应多个下标，映射关系根本理不清。用下标作为栈元素，天然规避了这个问题，还能通过temperatures[stack.peek()]随时访问对应温度，等于同时拿到了“值”和“位置”两个信息。

4.3 while 和 if 的区别，直接影响答案完整性

代码里最容易被“优化”坏的一行就是while。有人觉得栈顶只有一个，用if就够了；有人为了省一次循环把while改成if，然后遇到连续弹出的用例就出错。

我建议你在脑子里建立一个画面：新的高温就像一个“来解答问题的人”，它站在栈前面，把栈里所有“温度比自己低且正在等待”的人一个一个送走，直到遇到一个温度比自己高或者相等的人才停下来。这个过程天然是循环的。只有while才能表达“连续解答多个等待者”的语义。如果你只弹一个，相当于这个人只解答了一个人就走了，剩下的人还在傻等，显然不对。

4.4 残留栈元素与数组默认值的配合

遍历结束后，栈里剩下的下标都是“后面没有更高温度”的天数。有些同学会在循环结束时再写一段代码，把栈清空并将对应答案设置为 0。这样做结果没错，但完全多余——ans数组初始化时默认就是 0。

如果你犯过“手动清空栈并重置答案”，可以想想是不是因为之前用过某些语言的初始化行为不明确。Java 的int[]默认是 0，Python 的[0] * n也默认是 0，所以最后的残留栈元素不需要任何额外操作。这也是这道题一个很舒服的特性：你只管在遇到更高温度时写入答案，剩下的交给默认值即可。

5. 机考实战：从“会做题”到“稳稳拿分”

5.1 先看数据范围，再定算法

上机笔试和平时刷题有一个很重要的区别：评测数据是固定的，你没法通过“重跑一次”来碰运气。所以拿到题的第一步不是写代码，而是看约束条件。

以这道题为例，如果n <= 1000，暴力解完全够用，代码还更短、更不容易写错，没必要强行上单调栈。但如果n <= 10^5，暴力就是死路一条。这时候单调栈是最优解，时间复杂度 O(n)，空间复杂度 O(n)。刷题刷多了你会发现，很多“看起来很难”的题，约束条件一亮出来，算法选型基本就定了。这也是机考里最朴素的经验：复杂度估算要快、要准。10^5这个量级基本就是在告诉你，O(n) 和 O(n log n) 可以考虑，O(n^2) 一定超时。

5.2 自测用例别只测示例

很多同学在本地跑通示例就急着提交，结果一交就错。原因很简单：示例数据往往太友好了。针对这道题，我建议你至少准备这样几组自测用例：

• 空数组：[]，期望返回[]。
• 单元素数组：[30]，期望返回[0]。
• 整体递增：[1, 2, 3, 4]，答案应该全是[1, 1, 1, 0]。
• 整体递减：[40, 30, 20, 10]，一个更高温度都没有，答案全是[0, 0, 0, 0]。
• 含相等连续值：[30, 30, 31, 31, 32]，重点验证相等温度不出栈。
• 最大值出现在中间：[60, 70, 50, 80]，验证一个高温连续解答多个等待者的场景。

第 5 组最容易暴露问题。很多错误版本在单调递增和递减用例下都能碰巧通过，但一遇到重复值和中间高值，问题立刻现形。

5.3 笔试现场的时间分配技巧

机考和平时 IDE 里刷题还有一点不同：你需要在有限时间内完成读题、编码、调试三件事。我的建议是，像“每日温度”这样已经形成条件反射的经典题，目标是 10 分钟内写完并跑通。如果你在考场上第一次见这题，也建议先花两分钟把暴力解在草稿上写出来，不是为了提交，而是用来验证单调栈版本的正确性。用暴力解的输出作为标准答案，拿示例数据和自测数据两个版本对拍，这是一种非常可靠的验证方式。

笔试结束后，如果遇到的是这类“下一更大元素”思想的变体，比如环形数组、二维矩阵版的类似问题，保留这套单调栈框架，往往只需要改动循环范围和比较条件就能复用。这也是为什么我一直觉得，把一道经典题的原理彻底吃透，比一口气刷十道类似的题更有价值。

个人经验是：这道题值得隔一段时间重做一次。第一次做的时候，重点理解“用下标入栈，用下标差记录答案”这个核心套路；过两周再做，重点体会“新元素主动解答等待者”这个主动视角；等你开始刷更复杂的单调栈问题时，再回头看这道题，你会发现自己已经能很自然地分析出栈里元素的单调性了。这种从“会做一道题”到“掌握一类模型”的转变，才是刷题真正的收获。