LeetCode 739每日温度：从暴力到单调栈的完整拆解

我刚开始刷单调栈这个专题的时候，也被“每日温度”这道题卡过一阵。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]; Deque<Integer> 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)？因为每个下标最多入栈一次、出栈一次，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]; Deque<Integer> 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 ans

Python 里要注意的一点是：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 提交出错后的排查顺序

如果你写完代码提交 WA（Wrong Answer），我一般按这个顺序排查：

1. 先跑示例用例，确认输出是否符合预期。
2. 跑[1, 1, 1, 1]，确认等值温度是否被正确处理。
3. 跑[1, 2, 3, 4]和[4, 3, 2, 1]，确认递增和递减序列是否合理。
4. 检查栈内存的是不是下标而不是温度。
5. 检查遍历方向是否和弹出条件配套。

这套流程用下来，十有八九能在两分钟之内定位问题。

5. 从一道题延伸出一类题：单调栈的模型与应用

5.1 题型识别：下一更大元素系列

LeetCode 739每日温度本质上是“下一个更大元素”问题的一个变种。同系列的题目还包括：

• LeetCode 496：下一个更大元素 I，两个数组，单调栈 + 哈希表
• LeetCode 503：下一个更大元素 II，循环数组，把数组翻倍模拟环
• LeetCode 84：柱状图中最大的矩形，单调栈 + 哨兵
• LeetCode 42：接雨水，虽然解法很多，但单调栈也完全可解

这些题的核心都是：在数组中找到每个元素左边或右边第一个比它大（或小）的元素，并计算距离、面积或直接取值。一旦你在每日温度里建立了"单调栈存下标、按单调性弹出、遇到更大元素结算"的思维模型，上面这些题都可以顺势拿下来。

5.2 实际业务场景中的映射

单调栈不只是面试题。举几个实际场景：

• 股票交易场景中，给定一支股票每天的价格，想知道每个交易日之后第一次涨价要等多少天，这就是每日温度的翻版。
• 服务器日志场景中，统计每个请求之后第一个响应时间更长的请求，本质上也是“下一个更大元素”的变体。
• 天气预报系统中，如果你要做“未来几天气温上升提示”，原始数据结构就和这个题一模一样。

所以别看它是 easy 题，背后的模型迁移能力非常强。所谓“算法思维”，很多就是从这种小问题里训练出来的。

5.3 多语言实现对比小结

单调栈代码本身不长，但不同语言写起来各有优劣。Java 需要写Deque的完整类型声明，略显啰嗦但运行性能稳定；Python 代码最简洁，适合快速验证思路；C++ 用vector<int> 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”，那道题只是把数组变成循环数组，解法核心完全一致。这种“趁热打铁”的连续刷法，比分散着刷十几道不同专题的题效果好得多。是，算法学习没有太多捷径，但把单点打穿的笨功夫，恰恰是最快的路。