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温度栈底→顶动作结算 answer073[] → [0]压栈—174[0] → [1]7473弹出0结算1-01压1ans[0]1275[1] → [2]7574弹出1结算1压2ans[1]1371[2] → [2,3]71≤75压栈—469[2,3] → [2,3,4]69≤71压栈—572[2,3,4] → [2] → [2,5]7269弹出4结算17271弹出3结算2压5ans[4]1, ans[3]2676[2,5] → [6]7672弹出5结算17675弹出2结算4压6ans[5]1, ans[2]4773[6] → [6,7]73≤76压栈—最终 answer [1,1,4,2,1,1,0,0]✅关键洞察第5天温度72一次性结算了两个等待者69→1天71→2天。一个“高个子”可以同时拯救多个“矮个子”这正是暴力做不到的信息复用。 代码实现Python JavaPython版classSolution:defdailyTemperatures(self,temperatures:List[int])-List[int]:nlen(temperatures)ans[0]*n# 默认0后面没有更高温度stack[]# 存下标温度从栈底到栈顶递减foriinrange(n):# 新温度比栈顶高 → 栈顶等到了它的“下一个更高温度”whilestackandtemperatures[i]temperatures[stack[-1]]:jstack.pop()ans[j]i-j# 结算相隔天数stack.append(i)# 今天入栈成为新的等待者returnansJava版classSolution{publicint[]dailyTemperatures(int[]temperatures){intntemperatures.length;int[]ansnewint[n];DequeIntegerstacknewArrayDeque();// 存下标for(inti0;in;i){while(!stack.isEmpty()temperatures[i]temperatures[stack.peek()]){intjstack.pop();ans[j]i-j;}stack.push(i);}returnans;}}⚠️关键细节必看存下标不是存值——因为要算“相隔几天”下标差存值拿不到位置。不是相等不算“更高温度”用会错误结算相等元素。栈内剩余元素等不到更高温度保持默认0无需额外处理。⏱️ 复杂度分析面试必问时间O(n)每个元素至多入栈一次、出栈一次均摊O(1)。表面有while嵌套但总操作数O(n)。空间O(n)栈最坏存n个下标单调递减数组。 举一反三4道高频变种题一套模板通吃题目变化点思路调整LC.496 下一个更大元素Inums1是nums2的子集先对nums2全量求“下一个更大”存入Map再查nums1LC.503 下一个更大元素II循环数组把数组“虚拟拉长两倍”下标取模扫2n次LC.84 柱状图中最大矩形求最大矩形面积单调栈找左右第一个更矮的边界O(n)算面积比每日温度复杂一层LC.42 接雨水求能接多少雨水单调递减栈弹出时按“左右边界取min减底”结算水量 面试追问模拟提前准备Q1为什么栈里存下标而不是存值因为答案要的是“相隔几天”需要下标差。存值只知道温度不知道位置算不出距离。用下标可以通过temperatures[stack[-1]]随时取值信息量更大。Q2单调栈和单调队列有什么区别单调栈一端进出处理“下一个更大/更小元素”向右找第一个满足条件的邻居。单调队列两端操作双端队列处理“滑动窗口内的最值”窗口有左边界队首要过期弹出。记忆锚点“下一个”用单调栈“窗口”用单调队列。Q3为什么等于时不弹栈题目要求“下一个更高温度”相等不算。若用会错误地认为相等温度是“更高”答案偏小。只有严格大于才结算。Q4单调栈的核心思想能用一句话概括吗维护一个单调递减的“等待者”队列新来的“高个子”一次性结算所有比自己矮的“等待者”每个元素入栈出栈各一次。 实战小技巧刷题党必备口诀新来一个比栈顶高弹栈结算栈顶是等待者新来者是救星。模板凡是“找下一个更大/更小”的题优先单调栈。防坑存下标别存值比较用还是看题目语义。 实际应用场景不止是刷题股票/基金分析找下一个更高价判断卖出时机天气数据气温回升预测权限模型找下一个更高权限直方图渲染LC.84的工程版计算最大矩形面积 今日思考题如果题目改成“找下一个更小元素”代码需要改几个字符提示把改成其他完全不变。如果要求“循环数组的下一个更大元素”LC.503你又怎么改