xmlns="http://www.w3.org/2000/svg"

style="display:

none;">

学习笔记｜LeetCode

739

每日温度：从暴力枚举到单调栈线性最优解

一、问题回顾

给定每日气温数组temperatures，要求输出等长数组ans：

• ans[i]表示第i天之后，首次出现更高气温需要等待的天数；
• 若后续无更高气温，值为

  0。

问题本质：对数组中每个元素，找到右侧第一个更大元素，并计算下标间距。

二、基础实现：暴力枚举思路与局限

最直观的思路是暴力双重循环：

• 外层遍历每一天i；
• 内层从i+1向后遍历，找到第一个j满足temperatures[j]

  >

  temperatures[i]，记录j-i；

• 遍历结束未找到则赋值

  0。

//
暴力实现（示意）vector<int>dailyTemperatures(vector<int>&temperatures){intn=temperatures.size();vector<int>ans(n,0);for(inti=0;i<n;++i){for(intj=i+1;j<n;++j){if(temperatures[j]>temperatures[i]){ans[i]=j-i;break;}}}returnans;}

局限分析

时间复杂度O(N²)：当数组长度较大（如

10⁴

及以上）时，循环次数会急剧增加，出现明显性能瓶颈；同时内层循环存在大量重复比较，前序元素的比较结果未被复用，计算效率较低。

三、优化方向：状态复用与单调栈引入

暴力解法的核心问题是：每个元素会被多次比较，没有记录「尚未找到更大值的元素」的状态。

观察遍历过程：

• 我们从左到右遍历，先遍历到的元素，需要等待后遍历的元素来匹配「更大值」；
• 这种「先等待、后匹配」的场景，适合用栈保存未完成匹配的元素状态；
• 为了保证匹配效率，栈需要维持单调递减的特性：栈中元素从栈底到栈顶不递增，确保每次新元素入栈时，能直接找到所有可匹配的栈内元素。

四、单调栈解法：逻辑、实现与复杂度

核心思路

1. 栈中存储下标而非温度值：既可以通过下标获取温度，又能直接计算等待天数，避免额外存储；
2. 维护单调递减栈：栈内下标对应的温度，自底向上递减；
3. 遍历逻辑：
   • 若当前温度

     >

     栈顶下标对应温度，说明栈顶元素找到「右侧第一个更大值」；

   • 弹出栈顶下标，计算并赋值答案；
   • 重复上述过程，直到栈为空或栈顶温度不小于当前温度，再将当前下标入栈。

完整实现（C++）

classSolution{public:vector<int>dailyTemperatures(vector<int>&temperatures){intn=temperatures.size();vector<int>ans(n,0);stack<int>st;for(inti=0;i<n;++i){//
栈非空且当前温度更高，匹配栈顶元素while(!st.empty()&&temperatures[st.top()]<temperatures[i]){intidx=st.top();ans[idx]=i-idx;st.pop();}st.push(i);}returnans;}};

复杂度分析

• 时间复杂度

  O(N)：每个元素仅入栈、出栈各

  次，while

  循环的总执行次数与数组长度线性相关，无冗余计算；

• 空间复杂度

  O(N)：最坏情况下（数组严格递减），栈存储全部元素下标，空间与输入规模成正比。

五、工程实现中的细节与考量

1. 存储下标而非数值

   />若存储温度值，还需额外记录对应下标，增加内存开销与寻址步骤；直接存下标，一次存储即可满足「比较温度」「计算天数」两个需求，是更简洁的工程选择。

2. 栈结构的选型

   />标准库stack底层默认依赖deque，若追求更优的内存连续性，可改用vector模拟栈（用push_back/pop_back实现），在高频调用场景下，内存局部性更优。

3. 边界与特殊情况

   • 空数组、单元素数组：直接返回全

     数组，代码天然兼容；

   • 重复温度：栈的递减特性可正确处理，仅「严格更大」时匹配，符合题目要求。

4. 与实际业务场景的适配

   />该思路不局限于气温问题，可直接迁移到时序数据（股价、湿度、流量等）的「下一个更大值」场景，是处理单向时序匹配问题的通用线性解法。

六、知识迁移与小结

本题是**单调栈求解「下一个更大/更小元素」**的典型入门题：

• 核心是用栈保存「未完成匹配的状态」，通过单调特性避免重复比较，将平方复杂度优化为线性；
• 工程上优先考虑状态复用与存储效率，减少冗余计算与内存开销；
• 掌握这一思路后，可快速解决同类问题（如柱状图中最大矩形、接雨水、下一个更大元素

  I/II

  等）。