面试必看：每日温度

LeetCode 739. 每日温度 单调栈 详细题解

题目描述

给定一个整数数组temperatures，表示每天的气温。我们需要重新生成一个数组，对应位置的结果为：想要观测到更高气温，至少需要等待的天数。如果之后不会出现更高气温，则用 0 代替。

问题分析

本题本质是寻找每个元素右侧第一个比它大的元素，并记录两者之间的下标距离。
如果使用暴力双重循环，时间复杂度会达到 O(N²)，在数据量较大时容易超时。
观察遍历过程可以发现，我们需要为前面的元素等待一个更大值，这种“等待并比较”的场景非常适合使用单调栈来优化。

算法选择

这里选择单调递减栈：

• 栈中元素自底向上保持递减
• 遍历到新元素时，如果当前元素大于栈顶元素，说明找到了栈顶元素的“下一个更大元素”
• 弹出栈顶并计算天数，重复此过程直到栈重新保持单调

每个元素最多入栈和出栈各一次，时间效率远高于暴力解法。

解题思路

1. 定义一个栈，用于存储温度数组对应的下标，方便后续计算天数。
2. 定义结果数组ans，长度与温度数组一致，初始值为 0。
3. 遍历温度数组：
   • 当栈不为空，且栈顶下标对应的温度小于当前温度：
     • 弹出栈顶下标index
     • 结果数组对应位置赋值：ans[index] = i - index
   • 将当前下标压入栈中
4. 遍历结束后返回结果数组。

C++ 实现代码

classSolution{public:vector<int>dailyTemperatures(vector<int>&temperatures){intn=temperatures.size();vector<int>ans(n,0);stack<int>s;for(inti=0;i<n;i++){while(!s.empty()&&temperatures[s.top()]<temperatures[i]){intindex=s.top();ans[index]=i-index;s.pop();}s.push(i);}returnans;}};

复杂度分析

• 时间复杂度：O(N)
  每个元素仅入栈一次、出栈一次，虽然有两层循环，但整体仍为线性时间。
• 空间复杂度：O(N)
  最坏情况下栈存储所有元素，使用与数组长度相同的额外空间。

总结

本题是单调栈求下一个更大元素的经典应用，核心思路是利用栈保存未找到更大值的下标，遇到更大值时依次出栈并更新答案。掌握这种思路后，可以快速解决同类“下一个更大/更小元素”问题。