LeetCode 739. 每日温度——单调栈入门：下一个更大元素模板
LeetCode 739. 每日温度——单调栈入门：下一个更大元素模板
适读人群：Java 中级工程师、备战面试的同学 | 阅读时长：约20分钟 | 难度：中等
开篇故事
我记得刚做这道题的时候，脑子里第一反应是暴力双循环，写完提交，通过了，心想：这不挺简单的嘛。
直到某次组内代码评审，带我的老刘看了眼我的代码，没说话，只是用手指轻轻敲了两下桌子，然后在白板上写了两个字——单调栈。那一刻我才意识到，我会做题和我会做好题之间，差了整整一个数据结构的认知差距。
后来我专门花了两周时间把单调栈相关的题全刷了一遍，从最基础的每日温度，到股票跨度，到子数组最小值，再到天际线问题，慢慢摸出了一套通用的思维框架。在我看来，单调栈难不在实现，而在于认知——你要先知道在什么场景下该想到它。很多工程师刷了几百道题，见到「下一个更大元素」还是想不到单调栈，不是因为不会写，而是脑子里没有建立这个条件反射。
这篇文章就从最经典的入门题 LeetCode 739「每日温度」开始，把单调栈的核心思想和下一个更大元素的通用模板彻底讲透。我会从最朴素的暴力解法出发，一步步引导出单调栈的必要性，最后给出完整的代码实现和踩坑记录。不管你是第一次接触还是想系统复习，读完这篇，应该能建立起对单调栈的完整认知体系。
一、题目解析
题目描述：
给定一个整数数组 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天后。 对于第2天的75度，接下来依次是71、69、72，都没有超过75，直到第6天76度才超过，所以是4天后。
关键约束：
1 <= temperatures.length <= 10^530 <= temperatures[i] <= 100
这道题最朴素的理解就是：对于每个位置，找到它右边第一个比它大的位置。这是单调栈的经典应用场景——"下一个更大元素"问题。
为什么要想到单调栈？
当你看到题目里有「下一个更大/更小」「左边第一个比我大/小」这类描述，脑子里要条件反射：单调栈。这是一种能把 O(n²) 暴力优化到 O(n) 的利器。单调栈的本质是：用一个维护了单调性的栈来记录「还没有找到答案的元素」，当某个新元素进来打破单调性时，被弹出的元素就找到了自己的答案。这个过程保证了每个元素最多入栈一次、出栈一次，整体时间复杂度是线性的。
二、解法一：暴力双循环
思路分析
最直接的想法：对于每个位置 i，向右扫描找到第一个比 temperatures[i] 大的位置 j，答案就是 j - i。
这个思路没什么难度，代码直接写：
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] answer = new int[n];
for (int i = 0; i < n; i++) {
// 对每个位置，向右扫描寻找下一个更大的温度
for (int j = i + 1; j < n; j++) {
if (temperatures[j] > temperatures[i]) {
answer[i] = j - i;
break; // 找到第一个就停止
}
}
// 如果没找到，answer[i] 默认是 0，符合要求
}
return answer;
}
}复杂度分析
- 时间复杂度：O(n²)。最坏情况下（数组单调递减），对于每个位置都要扫描到末尾。比如
[5,4,3,2,1]，第0个位置要扫描5次，第1个位置扫描4次……总扫描次数是 n(n-1)/2，即 O(n²)。 - 空间复杂度：O(1)。只用了常数额外空间（不算输出数组）。
这个解法在数组长度不大时能通过，但 n = 10^5 时会超时。最坏情况下，10^5 个元素的双循环是 5 × 10^9 次操作，按 Java 每秒约 10^8 次操作计算，需要50秒，远远超出时限。
三、解法二：从右向左遍历 + 跳跃优化
思路分析
这是一种不太常见但很有意思的优化方式。如果我们从右往左处理，并且利用已经计算好的结果来加速查找，可以在一些场景下有不错的表现。
具体思路：从右向左遍历，对于位置 i，尝试利用 answer[i+1] 等已知结果来跳跃式查找下一个更大元素，而不是逐个比较。
这个优化的核心思想是：如果 temperatures[j] <= temperatures[i]，那么 j 的下一个更大温度出现的位置 j + answer[j] 对于 i 来说也可以作为候选。因为如果 j 处的温度都不够大，我们直接跳到 j 的答案位置，而不用一步一步扫描。
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] answer = new int[n];
// 从右向左遍历
for (int i = n - 2; i >= 0; i--) {
int j = i + 1;
// 利用已知结果进行跳跃查找
while (j < n && temperatures[j] <= temperatures[i]) {
if (answer[j] == 0) {
// j 之后没有更大的元素
j = n;
break;
}
j = j + answer[j]; // 跳跃到 j 的下一个更大位置
}
if (j < n && temperatures[j] > temperatures[i]) {
answer[i] = j - i;
}
}
return answer;
}
}复杂度分析
- 时间复杂度：均摊 O(n)。每个元素最多被跳跃访问常数次，整体上接近线性。严格证明比较复杂，但工程上表现优秀。
- 空间复杂度：O(1)。
这个解法有一定技巧性，但理解门槛较高，而且对于最坏情况（比如某些锯齿形序列）分析复杂。实际上对于这道题，单调栈才是最自然、最通用的解法，不需要这种跳跃技巧。
四、解法三（最优）：单调栈
核心思想
单调栈的精髓在于：维护一个栈，使得栈内元素始终保持单调性。
对于「下一个更大元素」问题，我们维护一个单调递减栈（栈底到栈顶的温度值递减）。
核心逻辑思路：
- 遍历数组，对于当前元素
cur和栈顶元素top进行比较 - 如果
cur > top，说明cur就是top一直在等待的「下一个更高温度」，弹出top并记录答案 - 重复步骤2，直到栈为空或栈顶元素对应的温度 >=
cur - 将
cur的下标入栈，等待后续更大的元素出现
为什么维护的是单调递减栈？
想象一下，我们站在某一天，向右看，我们关心的是什么时候温度比今天更高。栈里存的是「还没找到下一个更高温度的日子」，它们按时间顺序从栈底到栈顶排列，且温度是递减的。这里「温度递减」的含义是：如果某天的温度比它前面的某天更高，那前面那天就已经找到了答案（已经被弹出），不再留在栈里了。
Mermaid 流程图
完整代码
import java.util.Deque;
import java.util.ArrayDeque;
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] answer = new int[n];
// 单调递减栈：存储下标，栈内对应的温度单调递减
// 使用 ArrayDeque 作为栈（比 Stack 类性能更好）
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
// 当前温度比栈顶温度高，说明找到了栈顶元素的「下一个更大温度」
while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
int idx = stack.pop();
answer[idx] = i - idx;
}
// 将当前下标压入栈，等待后续出现更高温度
stack.push(i);
}
// 栈中剩余的元素，说明它们右边没有更大的温度
// answer 保持默认 0，不需要额外处理
return answer;
}
}手动模拟过程
以 temperatures = [73,74,75,71,69,72,76,73] 为例，详细演示每步操作：
| 步骤 | i | temp[i] | 栈（下标） | 操作说明 | answer更新 |
|---|---|---|---|---|---|
| 1 | 0 | 73 | [] | 栈空，压入0 | - |
| 2 | 1 | 74 | [0] | 74>73，弹出0；栈空，压入1 | answer[0]=1-0=1 |
| 3 | 2 | 75 | [1] | 75>74，弹出1；栈空，压入2 | answer[1]=2-1=1 |
| 4 | 3 | 71 | [2] | 71<75，不弹出，压入3 | - |
| 5 | 4 | 69 | [2,3] | 69<71，不弹出，压入4 | - |
| 6 | 5 | 72 | [2,3,4] | 72>69弹4；72>71弹3；72<75不弹2；压入5 | answer[4]=5-4=1, answer[3]=5-3=2 |
| 7 | 6 | 76 | [2,5] | 76>72弹5；76>75弹2；栈空；压入6 | answer[5]=6-5=1, answer[2]=6-2=4 |
| 8 | 7 | 73 | [6] | 73<76，不弹出，压入7 | - |
| 结束 | - | - | [6,7] | 剩余元素 answer 保持 0 | answer[6]=0, answer[7]=0 |
最终结果：[1,1,4,2,1,1,0,0]，与预期完全一致！
整个过程中，每个下标恰好入栈一次，出栈一次（或者留在栈中直到遍历结束），所以总操作次数是 2n，时间复杂度是 O(n)。
复杂度分析
- 时间复杂度：O(n)。每个元素最多入栈一次、出栈一次，总操作次数是 2n，所以是线性时间。这比暴力 O(n²) 有质的提升——对于 n=10^5，单调栈只需 2×10^5 次操作，而暴力需要 5×10^9 次。
- 空间复杂度：O(n)。最坏情况下（序列单调递减，如
[5,4,3,2,1]），所有元素都在栈中，空间占用 O(n)。
五、举一反三
掌握了每日温度之后，这一类「下一个更大元素」的题型都可以用同一个模板来解决。单调栈是一类题的钥匙，不仅仅是一道题的解法。
同类题目
| 题目 | 变体类型 | 关键点 |
|---|---|---|
| LeetCode 496. 下一个更大元素 I | 两个数组，查找映射 | 先对nums2建单调栈，再查询 |
| LeetCode 503. 下一个更大元素 II | 循环数组 | 数组长度翻倍，下标取模 |
| LeetCode 901. 股票价格跨度 | 在线处理数据流 | 单调栈存(price, span)对 |
| LeetCode 84. 柱状图中最大的矩形 | 双向扩展求面积 | 左右各维护一个单调栈 |
| LeetCode 85. 最大矩形（矩阵） | 逐行降维成84 | 每行构造柱状图后调用84 |
单调栈通用模板
// 模板一：找每个元素的下一个更大元素（单调递减栈）
public int[] nextGreaterElement(int[] nums) {
int n = nums.length;
int[] result = new int[n];
Arrays.fill(result, -1); // 默认找不到时的值
Deque<Integer> stack = new ArrayDeque<>(); // 存下标
for (int i = 0; i < n; i++) {
// 当前元素比栈顶大，弹出并记录答案
while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
int idx = stack.pop();
result[idx] = nums[i]; // 记录找到的下一个更大值
}
stack.push(i);
}
return result;
}
// 模板二：找下一个更小元素（单调递增栈）
public int[] nextSmallerElement(int[] nums) {
int n = nums.length;
int[] result = new int[n];
Arrays.fill(result, -1);
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
// 当前元素比栈顶小，弹出并记录答案
while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
int idx = stack.pop();
result[idx] = nums[i];
}
stack.push(i);
}
return result;
}记住这个口诀： 找下一个更大 → 递减栈（遇大则弹）；找下一个更小 → 递增栈（遇小则弹）。这两个方向记清楚了，单调栈一半的题就不会出错。
六、踩坑实录
这道题看起来简单，但实际写代码时有很多细节容易出错。我把自己和同事踩过的坑都列出来，希望你能少走弯路。
坑一：搞不清楚栈里存的是值还是下标
这是我刚学单调栈时踩的最大的坑。很多同学习惯把值存进栈，但其实几乎所有单调栈的题目都应该存下标。原因很简单：你最后要计算的往往是距离（j - i），或者要回头更新某个位置的结果，都需要知道下标。
存值的话你只能知道「这个位置的温度是多少」，存下标的话你既能通过 temperatures[idx] 拿到值，也能知道位置，信息量更大。而且存值在有重复元素时还会出现歧义（比如有两个73度，分不清是哪一天）。
错误写法：
// 不推荐：存值
Deque<Integer> stack = new ArrayDeque<>();
stack.push(temperatures[i]); // 后面就没法算距离了正确写法：
// 推荐：存下标
Deque<Integer> stack = new ArrayDeque<>();
stack.push(i); // 通过 temperatures[stack.peek()] 可以取到值坑二：Deque 当栈用时，push/pop 方向容易搞混
Java 里用 ArrayDeque 模拟栈时，要注意：push 相当于 addFirst（头插），pop 相当于 removeFirst（头删），peek 相当于 peekFirst（查看头部）。这些操作都在队列头部进行，用来模拟栈是完全正确的，因为栈是后进先出，头部既是入口也是出口。
但千万不要混用 add/remove（这是从尾部操作，是队列语义）。如果 push 用头部插入，remove 用尾部删除，方向就完全反了，整个栈的逻辑都是错的。
// 统一用栈语义 API，不要混搭
stack.push(i); // addFirst：入栈（头部）
stack.pop(); // removeFirst：出栈（头部）
stack.peek(); // peekFirst：查栈顶（头部）
// 或者统一用队列尾部模拟栈（也是一种合法写法）
stack.addLast(i); // 入栈（尾部）
stack.removeLast(); // 出栈（尾部）
stack.peekLast(); // 查栈顶（尾部）两套 API 都可以，关键是不要混用。我个人更喜欢 push/pop/peek，语义上就是栈，比较清晰。
坑三：循环结束后忘记处理栈中剩余元素
对于本题，栈中剩余的元素表示它们右边没有更大的温度，答案应该是0。幸运的是 Java 数组默认初始化为0，所以不用处理。
但如果题目要求的不是「找不到就是0」，而是「找不到就是-1」或「找不到就是自身」，就必须在循环后处理栈中剩余元素。我见过好几个同学在这上面丢分，代码主逻辑完全正确，就是最后这个细节没注意到，导致某些测试用例失败。
// 如果需要对找不到的情况赋特殊值：
int[] answer = new int[n];
Arrays.fill(answer, -1); // 先全填-1（默认找不到）
// 主循环 ...（逻辑不变）
// 或者循环后处理：
while (!stack.isEmpty()) {
answer[stack.pop()] = -1; // 或者赋其他默认值
}坑四：严格大于还是大于等于的边界问题
这道题是「更高温度」，即严格大于。但有些变体题目是「不低于」，即大于等于。这个边界条件非常容易出错，必须仔细读题。
temperatures[i] > temperatures[stack.peek()]：严格大于时弹出（本题）temperatures[i] >= temperatures[stack.peek()]：大于等于时弹出（某些变体）
两种写法的区别：严格大于的条件下，相同温度不会触发弹出，意味着「相同温度」的情况被视为「没有找到更高温度」。而大于等于的条件下，相同温度也会触发弹出，被视为「找到了同等温度」。
选择哪个取决于题目对「更大」的定义是否包含「相等」。
七、总结
今天把 LeetCode 739「每日温度」从暴力解法一步步推导到单调栈最优解，系统建立了单调栈解决「下一个更大元素」问题的思维框架。
核心要点回顾：
适用场景识别方面：看到「下一个更大/更小」「左/右第一个比我大/小」的关键词，优先想到单调栈，这是一种能把 O(n²) 降到 O(n) 的强力工具。
两种单调栈形态方面，需要区分清楚：单调递减栈用于找下一个更大元素，遇到更大的当前元素就把栈顶弹出；单调递增栈用于找下一个更小元素，遇到更小的当前元素就把栈顶弹出。方向记清楚，一半的单调栈题就不会出错。
实现要点方面要记住几点：栈里存下标不存值；用 ArrayDeque 模拟栈，统一用 push/pop/peek；注意严格大于还是大于等于；循环后要处理栈中剩余元素（本题默认为0可以不处理，但要知道这个细节）。
复杂度方面，时间 O(n)，空间 O(n)，相比暴力 O(n²) 有质的提升。对于 n=10^5 的输入，暴力会超时，单调栈轻松通过。
单调栈是一种很难在第一眼就想到的数据结构，但只要见到足够多的题型，条件反射就会慢慢建立起来。下一篇我们会处理循环数组版本的下一个更大元素（LeetCode 496+503），会有新的技巧加进来。
附录：单调栈的工程应用思考
在实际工程中，单调栈的应用场景比刷题时想象的要广泛得多。举几个我在工作中真实遇到过的场景：
场景一：股票回撤分析
金融系统里经常需要分析「从某个价格高点到下一个更低价格点的回撤」，这就是找「下一个更小元素」，单调递增栈直接套用。实时行情系统里，这个操作每天要跑几千万次，O(n) 和 O(n²) 的差距是真实可感知的延迟差异。
场景二：日志告警的静默期计算
有一个告警系统，每次告警触发后需要计算「下次这个告警还会重新触发是什么时候」。这和每日温度的「下一个更高温度」本质上是一样的问题，只不过是告警级别替代了温度，时间戳替代了下标。用单调栈，几乎不改代码就能复用整套逻辑。
场景三：任务调度的优先级队列
任务调度系统里，每个任务有优先级，需要找「下一个比当前任务优先级更高的任务」来决定是否抢占。这仍然是单调栈的变体，只是元素类型从整数变成了任务对象，比较条件从温度变成了优先级。
这些场景说明了一个道理：算法不只是面试技巧，它是解决实际问题的工具。把单调栈理解透了，遇到类似的工程问题，你脑子里自然会出现这个工具，而不是下意识写双层循环。
关于 Java 实现的性能注意事项
在 Java 中，ArrayDeque 比 Stack 和 LinkedList 都要快，因为它基于动态数组实现，不需要频繁的内存分配，且缓存友好。对于单调栈这种高频操作的数据结构，选择正确的容器类型能带来显著的性能提升。
在高并发场景下，如果多线程共享同一个单调栈，需要用 Deque 的线程安全实现，或者为每个线程维护独立的栈。但通常单调栈的使用场景是单线程计算，不存在并发问题。
另外，如果数据量特别大（比如亿级别），可以考虑用原始类型的 int[] 手动实现栈，避免 Integer 装箱开销：
// 用数组手动模拟栈，避免装箱开销
int[] stackArr = new int[n];
int top = -1; // 栈顶指针
// 入栈
stackArr[++top] = i;
// 出栈
int idx = stackArr[top--];
// 查看栈顶
int peek = stackArr[top];对于 LeetCode 题目而言，ArrayDeque 完全够用。但在工程实践中，如果性能是关键指标，手写数组栈是值得考虑的优化方向。