LeetCode 739. 每日温度 单调栈 详细题解题目描述给定一个整数数组temperatures表示每天的气温。我们需要重新生成一个数组对应位置的结果为想要观测到更高气温至少需要等待的天数。如果之后不会出现更高气温则用 0 代替。问题分析本题本质是寻找每个元素右侧第一个比它大的元素并记录两者之间的下标距离。如果使用暴力双重循环时间复杂度会达到 O(N²)在数据量较大时容易超时。观察遍历过程可以发现我们需要为前面的元素等待一个更大值这种“等待并比较”的场景非常适合使用单调栈来优化。算法选择这里选择单调递减栈栈中元素自底向上保持递减遍历到新元素时如果当前元素大于栈顶元素说明找到了栈顶元素的“下一个更大元素”弹出栈顶并计算天数重复此过程直到栈重新保持单调每个元素最多入栈和出栈各一次时间效率远高于暴力解法。解题思路定义一个栈用于存储温度数组对应的下标方便后续计算天数。定义结果数组ans长度与温度数组一致初始值为 0。遍历温度数组当栈不为空且栈顶下标对应的温度小于当前温度弹出栈顶下标index结果数组对应位置赋值ans[index] i - index将当前下标压入栈中遍历结束后返回结果数组。C 实现代码classSolution{public:vectorintdailyTemperatures(vectorinttemperatures){intntemperatures.size();vectorintans(n,0);stackints;for(inti0;in;i){while(!s.empty()temperatures[s.top()]temperatures[i]){intindexs.top();ans[index]i-index;s.pop();}s.push(i);}returnans;}};复杂度分析时间复杂度O(N)每个元素仅入栈一次、出栈一次虽然有两层循环但整体仍为线性时间。空间复杂度O(N)最坏情况下栈存储所有元素使用与数组长度相同的额外空间。总结本题是单调栈求下一个更大元素的经典应用核心思路是利用栈保存未找到更大值的下标遇到更大值时依次出栈并更新答案。掌握这种思路后可以快速解决同类“下一个更大/更小元素”问题。