学习笔记｜LeetCode 739 每日温度：从暴力枚举到单调栈线性最优解
学习笔记｜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⁴ 及以上）时，循环次数会急剧增加，出现明显性能瓶颈；同时内层循环存在大量重复比较，前序元素的比较结果未被复用，计算效率较低。
三、优化方向：状态复用与单调栈引入
暴力解法的核心问题是：每个元素会被多次比较，没有记录「尚未找到更大值的元素」的状态。
观察遍历过程：
- 我们从左到右遍历，先遍历到的元素，需要等待后遍历的元素来匹配「更大值」；
- 这种「先等待、后匹配」的场景，适合用栈保存未完成匹配的元素状态；
- 为了保证匹配效率，栈需要维持单调递减的特性：栈中元素从栈底到栈顶不递增，确保每次新元素入栈时，能直接找到所有可匹配的栈内元素。
四、单调栈解法：逻辑、实现与复杂度
核心思路
- 栈中存储下标而非温度值：既可以通过下标获取温度，又能直接计算等待天数，避免额外存储；
- 维护单调递减栈：栈内下标对应的温度，自底向上递减；
- 遍历逻辑：
- 若当前温度 > 栈顶下标对应温度，说明栈顶元素找到「右侧第一个更大值」；
- 弹出栈顶下标，计算并赋值答案；
- 重复上述过程，直到栈为空或栈顶温度不小于当前温度，再将当前下标入栈。
完整实现（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)：每个元素仅入栈、出栈各 1 次，while 循环的总执行次数与数组长度线性相关，无冗余计算；
- 空间复杂度 O(N)：最坏情况下（数组严格递减），栈存储全部元素下标，空间与输入规模成正比。
五、工程实现中的细节与考量
存储下标而非数值
若存储温度值，还需额外记录对应下标，增加内存开销与寻址步骤；直接存下标，一次存储即可满足「比较温度」「计算天数」两个需求，是更简洁的工程选择。栈结构的选型
标准库stack底层默认依赖deque，若追求更优的内存连续性，可改用vector模拟栈（用push_back/pop_back实现），在高频调用场景下，内存局部性更优。边界与特殊情况
- 空数组、单元素数组：直接返回全 0 数组，代码天然兼容；
- 重复温度：栈的递减特性可正确处理，仅「严格更大」时匹配，符合题目要求。
与实际业务场景的适配
该思路不局限于气温问题，可直接迁移到时序数据（股价、湿度、流量等）的「下一个更大值」场景，是处理单向时序匹配问题的通用线性解法。
六、知识迁移与小结
本题是**单调栈求解「下一个更大/更小元素」**的典型入门题：
- 核心是用栈保存「未完成匹配的状态」，通过单调特性避免重复比较，将平方复杂度优化为线性；
- 工程上优先考虑状态复用与存储效率，减少冗余计算与内存开销；
- 掌握这一思路后，可快速解决同类问题（如柱状图中最大矩形、接雨水、下一个更大元素 I/II 等）。