BMC开发修改代码流程(devtool 使用)
2026/6/6 11:31:26
读完本文你将了解：单调栈的核心原理 | AI 从暴力到 O(n) 的优化路径 | 这题其实是 Next Greater Element 的变体
📋 题目
原题：给定一个整数数组 temperatures，表示每天的温度，返回一个数组 answer，其中 answer[i] 表示需要等待多少天后才会有更高的温度。如果之后都不会升高，answer[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 |
输出解读：第 0 天 73 度，等 1 天到第 1 天 74 度就升温了；第 2 天 75 度，要等 4 天才遇到第 6 天的 76 度。
💡 先问一个问题
如果让 ChatGPT 第一次看到这道题，它会怎么写？
答案是——双重 for 循环，O(n²)。不是 AI 笨，这题长得就像「往后找」，嵌套循环是最直接的翻译。不过 10⁵ 个元素走 O(n²) 会超时，得换个思路。
🤖 第一版：AI 的朴素解法
defdailyTemperatures(temperatures):n=len(temperatures)answer=[0]*nforiinrange(n):forjinrange(i+1,n):iftemperatures[j]>temperatures[i]:answer[i]=j-ibreakreturnanswerAI 为什么会这样写？因为它看到「从当前位置往后找」，直观翻译成嵌套循环。逻辑正确，但复杂度 O(n²)，长度为 10⁵ 时 ≈ 50 亿次比较，LeetCode 直接 TLE。
🧠 AI 的自我优化：从暴力到单调栈
有意思的部分来了——AI 发现超时后，自己提出了一个关键洞察：
「我真正关心的不是后面的每一个数，而是第一个大于当前数的位置。」
第一轮优化：倒序 + 跳跃扫描
defdailyTemperatures(temperatures):n=len(temperatures)ans=[0]*nforiinrange(n-2,-1,-1):j=i+1whiletemperatures[j]<=temperatures[i]andans[j]>0:j+=ans[j]# 跳过已知不会升温的天数iftemperatures[j]>temperatures[i]:ans[i]=j-ireturnans这个优化利用了答案数组本身来跳过无效比较：如果ans[j] > 0，说明第 j 天后有更高温度，可以直接跳到那个位置。平均 O(n)，最坏 O(n²)——虽然还不够，但思路已经很接近了。
最终方案：正向扫描 + 单调递减栈
defdailyTemperatures(temperatures):n=len(temperatures)ans=[0]*n stack=[]# 存的是下标，温度严格递减foriinrange(n):whilestackandtemperatures[i]>temperatures[stack[-1]]:prev=stack.pop()ans[prev]=i-prev stack.append(i)returnansO(n) 时间，O(n) 空间。每个元素最多入栈一次、出栈一次，总操作 2n 次。这版代码是 LeetCode 最优解。
☕ Java 实现
publicint[]dailyTemperatures(int[]temperatures){intn=temperatures.length;int[]ans=newint[n];Deque<Integer>stack=newArrayDeque<>();for(inti=0;i<n;i++){while(!stack.isEmpty()&&temperatures[i]>temperatures[stack.peek()]){intprev=stack.pop();ans[prev]=i-prev;}stack.push(i);}returnans;}为什么要加 Java？CSDN 第一大用户群体是 Java 开发者。两版代码摆在一起，Java 工程师也能直接上手。
🔍 单调栈：这个模式到底在解决什么问题
单调栈的本质一句话：维护一个单调递增/递减的序列，用来快速找到下一个比自己大（或小）的元素。
这道题就是「Next Greater Element」的变体——把气温换成数字，完全一样。
单调栈三板斧：
| 题目类型 | 单调方向 | 栈里存什么 |
|---|---|---|
| 下一个更大元素（Daily Temperatures） | 递减栈 | 下标 |
| 下一个更小元素 | 递增栈 | 下标 |
| 区间范围（Largest Rectangle） | 递增栈 | 下标 |
记住：要找「下一个更大的」，就维护递减栈，当前值大于栈顶就出栈。
🏗️ 真实产品场景
这题换个皮就能上线：
股票价格跨度分析：你正在做一个股票 App 的「单调数据」模块，用户选中某个交易日，你需要告诉他「股价还要跌多少天才会反弹」。这就是 Daily Temperatures 换了个壳。
天气预报跨度：墨迹天气的「未来一周温度走势」里，"还要冷几天才回暖"这个功能，底层就是一个单调栈。
服务器负载监控：运维面板上，CPU 使用率持续走低，运维想知道「以当前趋势，什么时候负载会超过阈值」。把每日 CPU 数据喂给单调栈，直接出结果。
✅ 面试官的点评
- 基础通过线：能写出暴力法，分析出 O(n²)，说出会超时。
- 加分项：主动提到「单调栈」，解释清为什么递减栈能解决问题。
- 高分段：一上来就用单调栈，说清楚「每个元素最多进出一次栈，所以是 O(n)」，并用 Daily Temperatures 类比 Next Greater Element。
- 常见踩坑：栈里存的是温度值而不是下标，导致无法计算天数差。
📊 同类题推荐
- LeetCode 496 · Next Greater Element I— 最基本的单调栈入门，两个数组。
- LeetCode 503 · Next Greater Element II— 循环数组版本，拼接数组后照常处理。
- LeetCode 84 · Largest Rectangle in Histogram— 单调栈的进阶应用，用递增栈找区间边界。
来源说明：
- ✅ 已验证：LeetCode 739 官方题解 + ChatGPT / Claude 实测
- 📄 算法参考：《算法导论》单调栈章节