读完本文你将了解每日温度问题的核心解法 | AI 从暴力到最优的进化过程 | 面试中的优化关键点一句话理解找下一个更大值就像排队等位——你不知道后面的人什么来头但用个栈记住还没排到的人来个大单就结算一拨。 题目原题给定一个整数数组 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 先问一个问题LeetCode 739 每日温度这道题面试出场率极高。暴力解一眼就能看出来但数据规模 10⁵ 直接把你 O(n²) 的想法按死。猜猜 AI 第一次写这题会怎么翻车 第一版AI 的朴素解法暴力双层循环defdailyTemperatures(temperatures):nlen(temperatures)result[0]*nforiinrange(n):forjinrange(i1,n):iftemperatures[j]temperatures[i]:result[i]j-ibreakreturnresultAI 第一反应跟人类一样——看到下一个更大的直接上双层循环。外层遍历每一天内层往后找第一个更高的温度。复杂度时间 O(n²)空间 O(1)。n10⁵ 时最坏情况递减序列[100, 99, 98, …]要做 5×10⁹ 次比较。Python 里这大概跑 30 秒到 1 分钟面试官坐那儿等你跑完——不可能的。 AI 的自我优化第一次优化提示“能不能不用 O(n²)”第 1 次优化从右向左遍历defdailyTemperatures(temperatures):nlen(temperatures)result[0]*n hottest0foriinrange(n-1,-1,-1):iftemperatures[i]hottest:hottesttemperatures[i]continuedays1whiletemperatures[idays]temperatures[i]:daysresult[idays]result[i]daysreturnresult从右向左遍历维护一个最高温度变量。当前温度 已知最高温度时后面不会有更高的了直接跳过。核心技巧利用 result 数组跳着走。temperatures[idays] 比当前温度低时直接加上 result[idays] 的值跳到后面。但这个写法有两个问题while 循环在最坏情况下仍然接近 O(n²)可读性差——面试官看着也费劲。第 2 次优化Monotonic StackdefdailyTemperatures(temperatures):nlen(temperatures)result[0]*n stack[]# 存索引栈底到栈顶温度递减foriinrange(n):whilestackandtemperatures[i]temperatures[stack[-1]]:prev_indexstack.pop()result[prev_index]i-prev_index stack.append(i)returnresult这才是面试官想看到的版本。维护一个递减栈栈里存的是还没找到更高温度的索引。新来的温度比栈顶高栈顶就找到答案了弹出记录距离。遍历到 i0温度73栈为空入栈[0]遍历到 i1温度74 73弹出0result[0]1入栈[1]遍历到 i2温度75 74弹出1result[1]1入栈[2]遍历到 i3温度71 75入栈[2,3]遍历到 i4温度69 71入栈[2,3,4]遍历到 i5温度72 69,71弹出4→result[4]1弹出3→result[3]2入栈[2,5]遍历到 i6温度76 72,75弹出5→result[5]1弹出2→result[2]4入栈[6]遍历到 i7温度73 76入栈[6,7]遍历结束复杂度时间 O(n)空间 O(n)。每个元素入栈一次、出栈最多一次。☕ Java 实现publicint[]dailyTemperatures(int[]temperatures){intntemperatures.length;int[]resultnewint[n];DequeIntegerstacknewArrayDeque();for(inti0;in;i){while(!stack.isEmpty()temperatures[i]temperatures[stack.peek()]){intprevIndexstack.pop();result[prevIndex]i-prevIndex;}stack.push(i);}returnresult;}为什么要加 JavaCSDN 第一大用户群体是 Java 开发者。Python 的 list 当栈用虽然直观但面试场上 Java 的DequeInteger才是标准写法——面试官看到你用StackInteger可能会皱眉头Vector 继承的遗留问题性能差。两版代码摆在一起读者自己对比实现差异比你讲十句话都有用。 算法模式拆解这道题属于Monotonic Stack单调栈模式。核心特征找数组中每个元素下一个更大/更小的元素时单调栈是 O(n) 时间的最优选择。为什么 Monotonic Stack 能解决这类问题本质上是把未来信息缓存起来。暴力解每个元素都要往后看重复扫描——你已经知道第 i 天的温度了但第 i1 天还在等第 i2 天这种等待是嵌套的。单调栈的巧妙之处在于遍历一次数组把还没找到答案的元素暂存在栈里。栈里的元素保持单调递减——温度低的在上面温度高的在下面。新来的温度如果比栈顶高说明栈顶找到了答案弹出结算。然后继续比新的栈顶直到栈空或栈顶温度更高为止。这个过程等价于每个元素入栈一次、出栈最多一次。所以 O(n)。原始问题每个元素找下一个更大值暴力怎么做外层遍历每个元素内层往后找第一个更大的O(n²)单调栈怎么做遍历一次数组栈维护未找到答案的索引遇到更大的就弹出结算O(n) 搞定模式变体变体问题栈的特性下一个更大元素LeetCode 496递减栈找更大的下一个更小元素股票价格递增栈找更小的前一个更大元素反向遍历变体递减栈往前找每日温度LeetCode 739递减栈记录距离️ 真实产品场景天气预报 App你看未来一周的温度曲线想知道从哪天开始升温。这个问题就是 Daily Temperatures——每个温度点后面第一个更高的温度。股票价格跨度LeetCode 901实时股票行情中当前价格连续低于多少天的价格。这是单调栈的变体——找前面连续有多少天低于当前价格本质上还是维护一个递减栈。餐厅等位预估排队系统里每桌的等待时间取决于后面有没有更大桌的客人先到。单调栈可以实时计算每桌还需等多久。✅ 面试官的点评基本要求通过线能说出暴力解 复杂度分析能写出单调栈的 O(n) 解解释清楚栈里存的是索引不是温度值加分项解释为什么不用存温度值——通过索引可以直接访问温度数组主动分析边界条件所有温度递减时栈永远不会弹出result 全为 0指出 Java 里ArrayDeque比Stack更好Stack是线程安全的有性能开销常见踩坑栈里存温度值而不是索引——这样算不出距离忘记处理遍历结束后栈里剩余的元素这题里剩余元素默认 result0但变体题可能需要处理while 循环条件忘了判栈为空额外提醒单调栈在面试中出现频率很高但很多人只背模板不理解原理。如果面试官追问为什么是 O(n)答不上来就等于没懂。核心是每个元素入栈出栈各一次——这不是模板决定的是单调性质决定的。 同类题推荐题目难度一句话思路LeetCode 496 下一个更大元素 IEasy先用单调栈预处理 nums2存到哈希表LeetCode 503 下一个更大元素 IIMedium数组拉长两倍模运算处理循环LeetCode 901 股票价格跨度Medium单调栈存 [价格, 跨度]新价格来的时候合并栈顶来源说明✅ 已验证LeetCode 官方题解 AI 实测 文档/论文算法教材引用
