变O(n))
LC.739每日温度，一道看起来人畜无害的题：给你每天的温度，问你“还要等几天才能遇到更高的温度”。
暴力做？对每一天往后扫一遍，最坏O(n²)，1e5的数据量直接TLE。
面试官想听的不是暴力，而是单调栈——用O(n)时间干掉这道题，顺便把“下一个更大元素”这一整个题型家族一网打尽。
更妙的是，它是单调队列的“孪生兄弟”——都靠单调性提前淘汰不可能当答案的候选。
今天把这套思想彻底打通。
📦 题目速览（30 秒读懂）
给定数组
temperatures，返回answer，其中answer[i]是第i天后第一个更高温度出现在几天后。如果之后不会升高，填0。示例：
[73,74,75,71,69,72,76,73]
输出：[1,1,4,2,1,1,0,0]约束：长度1e5，温度范围 30~100。O(n²)必挂。
🧠 核心思路：换一个视角——不是“我往哪看”，而是“谁来替我结算”
暴力为什么慢？
每天往后扫描，找到第一个比它高的。前面的扫描结果完全不能复用，每个位置都从零开始。
换个视角：等待者模型
想象你手里攥着一叠“等待升温”的票据（记录日期），每来一天的新温度，你就检查：这张新票能不能帮那些还在等的旧票“结算”？
- 如果新温度比某张旧票高，那这张旧票的“下一个更高温度”就是今天，结算它！
- 结算完后，这张旧票就可以扔掉了（它的使命已完成）。
而为了高效结算，你需要把票据按温度从低到高排好——温度最低的票据先被结算。
这就是单调栈的直觉：栈里存下标，温度从栈底到栈顶单调递减（栈顶最冷，最容易被结算）。
算法流程（三句话）
- 遍历每一天，温度
t = temperatures[i]； - 只要栈不为空 且
t > 栈顶对应温度，就把栈顶弹出结算：answer[栈顶] = i - 栈顶； - 把
i压入栈，成为新的“等待者”。
为什么每个元素只进出栈一次？因为一旦被弹栈结算，它就再也不会被访问了——它的答案已经找到。
所有元素总入栈n次、出栈n次，所以O(n)。
🖼️ 图解算法（手把手走一遍）
temperatures = [73,74,75,71,69,72,76,73]，栈存下标，温度单调递减（栈顶最小）：
| i | 温度 | 栈（底→顶） | 动作 | 结算 answer |
|---|---|---|---|---|
| 0 | 73 | [] → [0] | 压栈 | — |
| 1 | 74 | [0] → [1] | 74>73，弹出0结算1-0=1；压1 | ans[0]=1 |
| 2 | 75 | [1] → [2] | 75>74，弹出1结算1；压2 | ans[1]=1 |
| 3 | 71 | [2] → [2,3] | 71≤75，压栈 | — |
| 4 | 69 | [2,3] → [2,3,4] | 69≤71，压栈 | — |
| 5 | 72 | [2,3,4] → [2] → [2,5] | 72>69，弹出4结算1；72>71，弹出3结算2；压5 | ans[4]=1, ans[3]=2 |
| 6 | 76 | [2,5] → [6] | 76>72，弹出5结算1；76>75，弹出2结算4；压6 | ans[5]=1, ans[2]=4 |
| 7 | 73 | [6] → [6,7] | 73≤76，压栈 | — |
最终 answer =[1,1,4,2,1,1,0,0]✅
关键洞察（第5天）：温度72一次性结算了两个等待者（69→1天，71→2天）。一个“高个子”可以同时拯救多个“矮个子”，这正是暴力做不到的信息复用。
💻 代码实现（Python + Java）
Python版
classSolution:defdailyTemperatures(self,temperatures:List[int])->List[int]:n=len(temperatures)ans=[0]*n# 默认0：后面没有更高温度stack=[]# 存下标，温度从栈底到栈顶递减foriinrange(n):# 新温度比栈顶高 → 栈顶等到了它的“下一个更高温度”whilestackandtemperatures[i]>temperatures[stack[-1]]:j=stack.pop()ans[j]=i-j# 结算：相隔天数stack.append(i)# 今天入栈，成为新的等待者returnansJava版
classSolution{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()]){intj=stack.pop();ans[j]=i-j;}stack.push(i);}returnans;}}⚠️关键细节（必看）：
- 存下标，不是存值——因为要算“相隔几天”（下标差），存值拿不到位置。
>不是>=：相等不算“更高温度”，用>=会错误结算相等元素。- 栈内剩余元素（等不到更高温度）保持默认0，无需额外处理。
⏱️ 复杂度分析（面试必问）
- 时间O(n)：每个元素至多入栈一次、出栈一次，均摊O(1)。表面有while嵌套，但总操作数O(n)。
- 空间O(n)：栈最坏存n个下标（单调递减数组）。
🚀 举一反三：4道高频变种题，一套模板通吃
| 题目 | 变化点 | 思路调整 |
|---|---|---|
| LC.496 下一个更大元素I | nums1是nums2的子集 | 先对nums2全量求“下一个更大”存入Map，再查nums1 |
| LC.503 下一个更大元素II | 循环数组 | 把数组“虚拟拉长两倍”（下标取模），扫2n次 |
| LC.84 柱状图中最大矩形 | 求最大矩形面积 | 单调栈找左右第一个更矮的边界，O(n)算面积（比每日温度复杂一层） |
| LC.42 接雨水 | 求能接多少雨水 | 单调递减栈，弹出时按“左右边界取min减底”结算水量 |
💬 面试追问模拟（提前准备）
Q1：为什么栈里存下标而不是存值？
因为答案要的是“相隔几天”，需要下标差。存值只知道温度，不知道位置，算不出距离。用下标可以通过
temperatures[stack[-1]]随时取值，信息量更大。
Q2：单调栈和单调队列有什么区别？
- 单调栈：一端进出，处理“下一个更大/更小元素”（向右找第一个满足条件的邻居）。
- 单调队列：两端操作（双端队列），处理“滑动窗口内的最值”（窗口有左边界，队首要过期弹出）。
记忆锚点：“下一个”用单调栈，“窗口”用单调队列。
Q3：为什么等于时不弹栈？
题目要求“下一个更高温度”，相等不算。若用
>=会错误地认为相等温度是“更高”，答案偏小。只有严格大于才结算。
Q4：单调栈的核心思想能用一句话概括吗？
维护一个单调递减的“等待者”队列，新来的“高个子”一次性结算所有比自己矮的“等待者”，每个元素入栈出栈各一次。
🧩 实战小技巧（刷题党必备）
- 口诀：新来一个比栈顶高，弹栈结算；栈顶是等待者，新来者是救星。
- 模板：凡是“找下一个更大/更小”的题，优先单调栈。
- 防坑：存下标，别存值；比较用
>还是>=看题目语义。
📈 实际应用场景（不止是刷题）
- 股票/基金分析：找下一个更高价，判断卖出时机
- 天气数据：气温回升预测
- 权限模型：找下一个更高权限
- 直方图渲染：LC.84的工程版，计算最大矩形面积
🎁 今日思考题
如果题目改成“找下一个更小元素”，代码需要改几个字符？
提示：把>改成<，其他完全不变。如果要求“循环数组的下一个更大元素”（LC.503），你又怎么改？
