读完本文你将了解每日温度的核心解法 | Monotonic Stack 的推导过程 | 面试中的优化思路 题目原题给定一个整数数组 temperatures表示每天的温度返回一个数组 answer其中 answer[i] 是指对于第 i 天下一个更高温度出现在几天后。如果气温在这之后都不会升高请在该位置用 0 来代替。项目说明输入temperatures [73, 74, 75, 71, 69, 72, 76, 73]输出[1, 1, 4, 2, 1, 1, 0, 0]约束1 ≤ temperatures.length ≤ 10⁵30 ≤ temperatures[i] ≤ 100 先问一个问题给你一周的天气预报想知道从今天起还要几天才能回暖——你会怎么算猜猜 AI 第一次碰到这题会怎么写十有八九它会写出最直觉的解法——两重循环一天天往后找。 第一版AI 的朴素解法暴力枚举defdailyTemperatures(temperatures):nlen(temperatures)answer[0]*nforiinrange(n):forjinrange(i1,n):iftemperatures[j]temperatures[i]:answer[i]j-ibreakreturnanswerAI 这样写很自然——人类看到下一个更高的值第一反应就是往后找。复杂度分析时间 O(n²) 空间 O(1)当 n 10⁵ 时最坏情况温度递减需要 5×10⁹ 次比较——跑完大概要几分钟。面试官这时候通常会问“能优化吗” AI 的自我优化AI 意识到暴力解的问题在于大量重复比较。当温度序列是 [80, 79, 78, 77, 76, 75, 90] 时每个元素都在重复扫描那些明显比它低的元素。第 1 次优化反向遍历 跳跃defdailyTemperatures(temperatures):nlen(temperatures)answer[0]*nforiinrange(n-2,-1,-1):ji1whilejnandtemperatures[j]temperatures[i]:ifanswer[j]0:janswer[j]else:jnifjn:answer[i]j-ireturnanswer利用已经算好的 answer 值跳跃——如果 answer[j] 是 4说明 j 之后第 4 天才有更高的温度直接跳到那里不用逐个比较。但这只是取巧——最坏情况仍是 O(n²)。第 2 次优化Monotonic Stack正确答案defdailyTemperatures(temperatures):nlen(temperatures)answer[0]*n stack[]# 存下标温度单调递减foriinrange(n):whilestackandtemperatures[i]temperatures[stack[-1]]:prevstack.pop()answer[prev]i-prev stack.append(i)returnanswer核心思路维护一个单调递减的栈。遍历每个温度时如果它比栈顶温度高说明栈顶元素的下一个更高温度找到了弹出并计算结果。暴力枚举O(n²)逐个比较反向跳跃优化O(n)~O(n²)利用已算结果Monotonic StackO(n)每个元素入栈/出栈一次☕ Java 实现classSolution{publicint[]dailyTemperatures(int[]temperatures){intntemperatures.length;int[]answernewint[n];DequeIntegerstacknewArrayDeque();for(inti0;in;i){while(!stack.isEmpty()temperatures[i]temperatures[stack.peek()]){intprevstack.pop();answer[prev]i-prev;}stack.push(i);}returnanswer;}}CSDN 第一大用户群体是 Java 开发者。Python 看懂了不代表面试能用 Java 写出来——两版代码摆在一起读者自己对比比你讲十句话都有用。 算法模式拆解这道题属于Monotonic Stack单调栈模式。模式识别特征问题涉及下一个更大/更小的元素数组长度大10⁵ 级别O(n²) 不可行需要维护一个候选者集合且候选者之间有明显的大小关系为什么 Monotonic Stack 能解决这类问题是是否遍历到温度 76比栈顶 72 高弹出 72answer[5]1(76在72后1天)新的栈顶 69弹出 69answer[4]2(76在69后2天)栈顶 71 7676 入栈栈[71,76]每个元素最多入栈一次、出栈一次——O(n)。模式变体下一个更大元素Next Greater Element标准题型下一个更小元素Next Smaller Element单调递增栈股票价格跨度LeetCode 901变体题️ 真实产品场景这个算法在现实中的典型应用是天气预报系统的温度趋势计算。假设你做一个天气 App比如墨迹天气、彩云天气用户想看今天之后什么时候升温——后台服务每天要处理全国 3000 气象站的数据每个站一年 365 天的逐小时温度。用暴力解一个气象站就要 10⁴ × 10⁴ / 2 ≈ 5×10⁷ 次计算。用 Monotonic Stack每个站只需 O(n) 次全国 3000 个站的计算量从天文数字降到可接受范围。另一个场景电商平台的价格趋势分析。想知道某个商品从今天起什么时候降价——同一天内上万个 SKU 的价格变化用单调栈统一计算一次遍历搞定所有。✅ 面试官的点评通过标准能写出 O(n²) 暴力解 → 基础分60 分主动提出 Monotonic Stack 优化 → 通过80 分解释清楚为什么单调栈能保证每个元素只入栈出栈一次 → 加分90 分加分细节说明栈中存的是下标而不是值——方便计算天数差主动提到数组下标从 0 开始answer 长度与输入一致考虑边界情况空数组、只有一个元素、全递增/全递减常见踩坑用值入栈而不是下标 → 算不出天数差忘记处理栈中剩余元素单调栈里剩下的温度永远不会遇到更高温度 → answer 默认为 0 就对了在 Java 中用Stack类过时而不是Deque/ArrayDeque 同类题推荐题目难度一句话思路LeetCode 496. 下一个更大元素 IEasy单调栈找下一个更大值用哈希表存结果LeetCode 503. 下一个更大元素 IIMedium循环数组遍历 2n 次下标取模LeetCode 901. 股票价格跨度Medium单调栈存[价格, 跨度]每次弹出时累加跨度来源说明✅ 已验证LeetCode 官方题解 AI 实测