学习笔记LeetCode 739 每日温度从暴力枚举到单调栈线性最优解一、问题回顾给定每日气温数组temperatures要求输出等长数组ansans[i]表示第i天之后首次出现更高气温需要等待的天数若后续无更高气温值为 0。问题本质对数组中每个元素找到右侧第一个更大元素并计算下标间距。二、基础实现暴力枚举思路与局限最直观的思路是暴力双重循环外层遍历每一天i内层从i1向后遍历找到第一个j满足temperatures[j] temperatures[i]记录j-i遍历结束未找到则赋值 0。// 暴力实现示意vectorintdailyTemperatures(vectorinttemperatures){intntemperatures.size();vectorintans(n,0);for(inti0;in;i){for(intji1;jn;j){if(temperatures[j]temperatures[i]){ans[i]j-i;break;}}}returnans;}局限分析时间复杂度O(N²)当数组长度较大如 10⁴ 及以上时循环次数会急剧增加出现明显性能瓶颈同时内层循环存在大量重复比较前序元素的比较结果未被复用计算效率较低。三、优化方向状态复用与单调栈引入暴力解法的核心问题是每个元素会被多次比较没有记录「尚未找到更大值的元素」的状态。观察遍历过程我们从左到右遍历先遍历到的元素需要等待后遍历的元素来匹配「更大值」这种「先等待、后匹配」的场景适合用栈保存未完成匹配的元素状态为了保证匹配效率栈需要维持单调递减的特性栈中元素从栈底到栈顶不递增确保每次新元素入栈时能直接找到所有可匹配的栈内元素。四、单调栈解法逻辑、实现与复杂度核心思路栈中存储下标而非温度值既可以通过下标获取温度又能直接计算等待天数避免额外存储维护单调递减栈栈内下标对应的温度自底向上递减遍历逻辑若当前温度 栈顶下标对应温度说明栈顶元素找到「右侧第一个更大值」弹出栈顶下标计算并赋值答案重复上述过程直到栈为空或栈顶温度不小于当前温度再将当前下标入栈。完整实现CclassSolution{public:vectorintdailyTemperatures(vectorinttemperatures){intntemperatures.size();vectorintans(n,0);stackintst;for(inti0;in;i){// 栈非空且当前温度更高匹配栈顶元素while(!st.empty()temperatures[st.top()]temperatures[i]){intidxst.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 等。