想系统提升编程能力、查看更完整的学习路线欢迎访问 AI Compasshttps://github.com/tingaicompass/AI-Compass仓库持续更新刷题题解、Python 基础和 AI 实战内容适合想高效进阶的你。 第35课:每日温度模块:栈与队列 |难度:Medium ⭐⭐⭐LeetCode 链接:https://leetcode.cn/problems/daily-temperatures/前置知识:第33课(有效的括号)、第34课(最小栈)预计学习时间:25分钟 题目描述给定一个整数数组temperatures,表示每天的温度。请返回一个数组answer,其中answer[i]表示对于第i天,需要等待多少天才能出现更高的温度。如果之后没有更高的温度,则answer[i] 0。示例:输入:temperatures [73,74,75,71,69,72,76,73] 输出:[1,1,4,2,1,1,0,0] 解释: - 第0天(73°C):第1天就有更高温度(74°C),等待1天 - 第1天(74°C):第2天就有更高温度(75°C),等待1天 - 第2天(75°C):第6天才有更高温度(76°C),等待4天 - 第3天(71°C):第5天有更高温度(72°C),等待2天 - 第4天(69°C):第5天有更高温度(72°C),等待1天 - 第5天(72°C):第6天有更高温度(76°C),等待1天 - 第6天(76°C):后面没有更高温度,等待0天 - 第7天(73°C):后面没有更高温度,等待0天约束条件:1 ≤ temperatures.length ≤ 10^5 — 数据量大,要求O(n)时间复杂度30 ≤ temperatures[i] ≤ 100 — 温度范围有限,但不影响算法选择 边界用例(面试必考)用例类型输入期望输出考察点单调递减[100,99,98,97][0,0,0,0]全部无更高温度单调递增[30,31,32,33][1,1,1,0]每天都能立即等到最小输入[30][0]单日无比较对象重复温度[73,73,73][0,0,0]相同温度不算更高大规模10^5个元素—性能测试,必须O(n) 思路引导生活化比喻想象你每天早上看天气预报,想知道下一个暖和天还要等多久?笨办法:每天你都翻看后面所有日期的温度,逐个比较直到找到比今天暖和的那天。如果有30天数据,第1天要看29天,第2天要看28天…总共要看约450次,太累了!聪明办法:你维护一个待确认清单(栈),上面记录着还没找到答案的日期。每次看到新的温度,就帮清单上那些比它冷的日期找到答案。就像天气预报员用一个倒计时表,每天只看一次就能更新所有相关日期!关键洞察对于每个温度,我们要找它右边第一个更大的值 → 这是单调栈的经典应用场景! 解题思维链这一节模拟你在面试中从零开始思考的过程。Step 1:理解题目 → 锁定输入输出输入:整数数组 temperatures,表示每天温度,长度最多10^5输出:整数数组,每个位置记录需要等待的天数(下标差)限制:数据量大,暴力O(n²)会超时Step 2:先想笨办法(暴力法)对于每一天 i,从 i1 开始向右扫描,找到第一个比 temperatures[i] 大的位置 j,答案就是 j - i。如果扫描到末尾都没找到,答案就是 0。时间复杂度:O(n²) — 最坏情况每个位置都要扫描后面所有元素瓶颈在哪:向右扫描找更大值这一步对每个元素都要重复进行Step 3:瓶颈分析 → 优化方向暴力法的问题是:对于每个温度,我们都要重新扫描后面所有元素。但仔细想想:如果我们从右向左遍历,已经知道了右边的温度情况当遇到一个新温度时,可以利用已知信息快速判断核心问题:能否一边遍历一边维护一些待处理的元素,当条件满足时立即处理,而不是每次都全扫描?优化思路:用栈记录还没找到答案的日期,栈内保持单调递减,遇到更高温度时一次性处理多个日期Step 4:选择武器选用:单调递减栈(Monotonic Decreasing Stack)理由:栈可以后进先出,天然适合最近还没解决的问题维护递减顺序,保证遇到更高温度时能快速找到所有需要更新的日期每个元素只入栈、出栈一次,时间复杂度O(n)模式识别提示:当题目出现下一个更大/更小元素、“等待天数”、“股票价格跨度”,优先考虑单调栈模式 解法一:暴力枚举(朴素法)思路对每一天,从下一天开始向右扫描,直到找到第一个更高温度或到达末尾。图解过程示例: temperatures [73,74,75,71,69,72,76,73] Day 0 (73°C): 向右扫描 [73, 74, 75, 71, 69, 72, 76, 73] ↑ ↑ i 找到7473, 等待1天 Day 1 (74°C): 向右扫描 [73, 74, 75, 71, 69, 72, 76, 73] ↑ ↑ i 找到7574, 等待1天 Day 2 (75°C): 向右扫描 [73, 74, 75, 71, 69, 72, 76, 73] ↑ × × × ↑ i 7175, 6975, 7275, 找到7675, 等待4天 每天都要扫描后面所有元素,重复计算严重!Python代码fromtypingimportListdefdailyTemperatures_brute(temperatures:List[int])-List[int]: 解法一:暴力枚举 思路:对每一天,向右扫描找第一个更高温度 nlen(temperatures)answer[0]*n# 初始化答案数组,默认都是0# 对每一天进行处理foriinrange(n):# 从下一天开始向右扫描forjinrange(i1,n):iftemperatures[j]temperatures[i]:answer[i]j-i# 找到第一个更高温度,记录天数差break# 找到后立即停止# 如果循环结束都没找到,answer[i]保持为0returnanswer# ✅ 测试print(dailyTemperatures_brute([73,74,75,71,69,72,76,73]))# 期望输出:[1,1,4,2,1,1,0,0]print(dailyTemperatures_brute([30,40,50,60]))# 期望输出:[1,1,1,0]print(dailyTemperatures_brute([100,99,98,97]))# 期望输出:[0,0,0,0]复杂度分析时间复杂度(n²) — 外层循环n次,内层最坏扫描n次具体地说:如果输入规模 n10000,最坏需要约 10000×10000/2 5000万次操作,会超时!空间复杂度(1) — 只用了固定的几个变量,不算输出数组优缺点✅ 思路直观,容易理解,代码简单❌ 时间复杂度O(n²),数据量大时会超时❌ 大量重复扫描,效率低下 解法二:单调递减栈(最优解)优化思路暴力法的问题是每次都重新扫描,我们可以用栈来避免重复:从左向右遍历,用栈记录还没找到答案的日期索引栈内元素对应的温度保持递减,这样遇到更高温度时能一次性处理多个遇到更高温度时,弹出栈顶所有比它小的元素,计算天数差关键想法:维护一个待确认清单(栈),栈里是等待更高温度的日期。每次遇到新温度,检查它能否成为栈中某些日期的答案。图解过程示例: temperatures [73,74,75,71,69,72,76,73] 栈中存储的是日期索引,对应的温度保持递减 初始: stack[], answer[0,0,0,0,0,0,0,0] Day 0 (73°C): stack为空,直接入栈 stack[0] (对应温度73) Day 1 (74°C): 74 73 → 栈顶0的答案是1-01 弹出0, answer[0]1 stack为空,1入栈 stack[1] (对应温度74) answer[1,0,0,0,0,0,0,0] Day 2 (75°C): 75 74 → 栈顶1的答案是2-11 弹出1, answer[1]1 stack为空,2入栈 stack[2] (对应温度75) answer[1,1,0,0,0,0,0,0] Day 3 (71°C): 71 75 → 不弹出,3入栈 stack[2,3] (对应温度75,71 递减) answer[1,1,0,0,0,0,0,0] Day 4 (69°C): 69 71 → 不弹出,4入栈 stack[2,3,4] (对应温度75,71,69 递减) answer[1,1,0,0,0,0,0,0] Day 5 (72°C): 72 69 → 栈顶4的答案是5-41, 弹出4 72 71 → 栈顶3的答案是5-32, 弹出3 72 75 → 停止弹出,5入栈 stack[2,5] (对应温度75,72 递减) answer[1,1,0,2,1,0,0,0] Day 6 (76°C): 76 72 → 栈顶5的答案是6-51, 弹出5 76 75 → 栈顶2的答案是6-24, 弹出2 stack为空,6入栈 stack[6] (对应温度76) answer[1,1,4,2,1,1,0,0] Day 7 (73°C): 73 76 → 不弹出,7入栈 stack[6,7] (对应温度76,73) answer[1,1,4,2,1,1,0,0] 遍历结束,栈中剩余的[6,7]都没有更高温度,保持answer0 关键观察: 1. 每个索引只入栈一次、出栈一次 2. 栈内温度严格递减,保证了正确性 3. 一个更高温度可以一次性解决多个待确认日期Python代码defdailyTemperatures(temperatures:List[int])-List[int]: 解法二:单调递减栈(最优解) 思路:维护栈保持温度递减,遇到更高温度时处理所有比它小的 nlen(temperatures)answer[0]*n# 初始化答案数组stack[]# 栈中存储索引,对应的温度保持递减foriinrange(n):# 当前温度比栈顶温度高时,栈顶找到了答案whilestackandtemperatures[i]temperatures[stack[-1]]:prev_indexstack.pop()# 弹出栈顶索引answer[prev_index]i-prev_index# 计算天数差# 当前索引入栈stack.append(i)# 栈中剩余的索引都没有找到更高温度,answer保持为0returnanswer# ✅ 测试print(dailyTemperatures([73,74,75,71,69,72,76,73]))# 期望输出:[1,1,4,2,1,1,0,0]print(dailyTemperatures([30,40,50,60]))# 期望输出:[1,1,1,0]print(dailyTemperatures([100,99,98,97]))# 期望输出:[0,0,0,0]print(dailyTemperatures([30]))# 期望输出:[0]复杂度分析时间复杂度(n) — 每个元素最多入栈一次、出栈一次,总共2n次操作具体地说:如果输入规模 n10000,只需要约20000次操作,比暴力法快2500倍!为什么是O(n)而不是O(n²)?虽然有while循环嵌套,但每个元素入栈后最多被弹出一次,所以总的弹出次数不会超过n空间复杂度(n) — 最坏情况(单调递减数组)栈中存储所有n个索引为什么这是最优解?时间已达理论下限O(n)— 至少要遍历一遍数组,无法更优空间O(n)换来时间5000倍提升— 对于10^5规模数据,这个代价完全值得代码简洁清晰— 核心逻辑只有10行,面试中容易写对通用性强— 所有下一个更大/更小元素问题都能用这个模式 Pythonic 写法利用 enumerate 和列表推导式的简洁写法:defdailyTemperatures_pythonic(temperatures:List[int])-List[int]: Pythonic写法:使用enumerate增强可读性 nlen(temperatures)answer[0]*n stack[]fori,tempinenumerate(temperatures):whilestackandtemptemperatures[stack[-1]]:prev_indexstack.pop()answer[prev_index]i-prev_index stack.append(i)returnanswer这个写法用enumerate(temperatures)同时获取索引和温度值,代码更加清晰。但核心逻辑与标准版完全相同。⚠️面试建议:先写清晰版本展示思路,再提 Pythonic 写法展示语言功底。面试官更看重你的思考过程和算法理解,而非代码行数。 解法对比维度解法一:暴力枚举 解法二:单调栈(最优)时间复杂度O(n²)O(n)← 时间最优空间复杂度O(1)O(n)← 可接受代码难度简单中等(需理解单调栈)面试推荐⭐⭐⭐⭐← 首选适用场景仅适合小规模数据(n100)面试首选,通用性强,处理10^5数据无压力为什么是最优解:时间复杂度O(n)已经是理论最优(至少要遍历一遍所有元素)空间O(n)的代价换来时间5000倍的提升,完全值得单调栈是处理下一个更大/更小元素的标准模式,面试高频考点代码简洁清晰,面试中10分钟内能写出并测试通过面试建议:先用30秒口述暴力法思路(O(n²)),表明你能想到基本解法立即优化到最优解(O(n)单调栈),展示优化能力重点讲解最优解的核心思想:“维护栈内温度递减,遇到更高温度时一次性处理多个待确认日期”强调为什么这是最优:时间已达理论下限O(n),每个元素只入栈出栈一次手动用示例测试,演示栈的变化过程,展示对解法的深入理解 面试现场模拟面试中的完整对话流程,帮你练习边想边说。面试官:请你解决一下这道题。你:(审题30秒)好的,这道题要求计算每天需要等待多少天才能出现更高温度。让我先想一下…我的第一个想法是暴力法:对每一天,从下一天开始向右扫描,找到第一个更高温度。时间复杂度是 O(n²),对于10^5的数据量会超时。不过我们可以用单调递减栈来优化到 O(n)。核心思路是:维护一个栈,里面存储还没找到答案的日期索引,栈内对应的温度保持递减。当遇到更高温度时,可以一次性处理栈中所有比它小的温度,计算天数差。面试官:很好,请写一下代码。你:(边写边说关键步骤)defdailyTemperatures(temperatures):nlen(temperatures)answer[0]*n stack[]# 栈中存储索引foriinrange(n):# 当前温度比栈顶高时,栈顶找到了答案whilestackandtemperatures[i]temperatures[stack[-1]]:prev_indexstack.pop()answer[prev_index]i-prev_index stack.append(i)returnanswer关键在于这个while循环:当遇到更高温度时,持续弹出栈中所有比它小的索引,并计算天数差。最后当前索引入栈,保持栈内温度递减。面试官:测试一下?你:用示例 [73,74,75,71,69,72,76,73] 走一遍…Day 0 (73): 栈为空,0入栈Day 1 (74): 7473,弹出0并记录answer[0]1,然后1入栈Day 2 (75): 7574,弹出1并记录answer[1]1,然后2入栈Day 3 (71): 7175,3入栈,栈变为[2,3]…最终得到 [1,1,4,2,1,1,0,0],正确!再测一个边界情况 [100,99,98,97] (单调递减):所有温度依次入栈,最后都没弹出,答案全是0,正确!高频追问追问应答策略“为什么栈要保持递减?”“因为我们要找’下一个更大的’,如果栈内递增,遇到更大值时无法确定应该匹配哪个。递减栈保证了:遇到更大值时,从栈顶开始弹出的都是应该被它匹配的元素,且越靠近栈顶的越晚被匹配,符合’最近的更大值’的语义。”“空间能不能O(1)?”“不能。需要额外空间记录待处理状态。暴力法虽然O(1)空间,但O(n²)时间不可接受。工程中优先时间,O(n)空间换O(n)时间是值得的。”“如果求的是’上一个更大的’呢?”“从右向左遍历,同样用单调递减栈即可。或者从左向右遍历时用栈记录已处理元素,每次查找栈中第一个比当前大的。”“实际工程中怎么用?”“股票价格跨度、直方图最大矩形、表达式求值等。例如:股票今日价格能向前追溯到多少天(连续不高于今日的最长天数),就是单调栈的典型应用。” 知识点总结Python技巧卡片 # 技巧1:栈的高效操作 — list当栈用,append/pop时间O(1)stack[]stack.append(5)# 入栈topstack[-1]# 查看栈顶(不弹出)elementstack.pop()# 出栈# 技巧2:enumerate同时获取索引和值 — 比range(len())更清晰fori,tempinenumerate(temperatures):print(fDay{i}:{temp}°C)# 技巧3:列表初始化 — 创建固定长度的默认值列表answer[0]*n# 创建n个0的列表# 技巧4:while stack组合 — 处理连续满足条件的场景whilestackandcondition:# 持续弹出直到不满足条件elementstack.pop() 底层原理(选读)为什么单调栈能保证每个元素只入栈出栈一次?关键在于单调性:栈内元素对应的值保持递减。入栈时机:当前元素比栈顶小(或栈为空)时入栈出栈时机:遇到比栈顶大的元素时弹出栈顶唯一性保证:每个元素入栈后,只有在遇到第一个比它大的元素时才会被弹出,这个时刻最多发生一次所以总的操作次数 n次入栈 最多n次出栈 O(2n) O(n)为什么是递减栈而不是递增栈?因为我们要找下一个更大的元素。递减栈保证:栈顶是当前最小的还没找到答案的元素遇到更大值时,从栈顶开始弹出的元素都应该被这个更大值匹配如果用递增栈,遇到更大值时无法确定应该匹配谁(可能有多个候选)算法模式卡片 模式名称:单调递减栈(Monotonic Decreasing Stack)适用条件:需要找每个元素右边(或左边)第一个更大(或更小)的元素识别关键词:“下一个更大/更小元素”“等待天数/股票跨度”“直方图/柱状图中的矩形”“接雨水/积水问题”模板代码:defnext_greater_element(nums):单调递减栈模板 — 求每个元素右边第一个更大的元素nlen(nums)result[-1]*n# 默认-1表示没找到stack[]# 存储索引foriinrange(n):# 当前元素比栈顶大时,栈顶找到了答案whilestackandnums[i]nums[stack[-1]]:prev_indexstack.pop()result[prev_index]nums[i]# 或者 i - prev_index(记录距离)stack.append(i)returnresult# 变体:求左边第一个更大的 — 从右向左遍历即可# 变体:求下一个更小的 — 改为 nums[i] nums[stack[-1]]# 变体:循环数组 — 遍历两遍,用 i % n 取模易错点 ⚠️栈中存什么— 常见错误:直接存温度值为什么错:我们需要计算天数差,必须知道索引位置正确做法:栈中存储索引,通过temperatures[stack[-1]]获取对应温度边界条件处理— 常见错误:忘记初始化answer为0为什么错:栈中剩余的元素(没被弹出的)表示没有更高温度,应该是0正确做法:一开始初始化answer [0] * n,剩余的自然保持为0while条件判断— 常见错误:只用while stack为什么错:可能访问越界,或者死循环正确做法:while stack and temperatures[i] temperatures[stack[-1]]同时检查栈非空和温度条件理解单调性— 常见错误:认为栈内存储的温度必须严格递减为什么错:相等温度也可以,关键是不能递增正确做法:条件是temperatures[i] temperatures[stack[-1]],等于时不弹出️ 工程实战(选读)这个算法思想在真实项目中的应用,让你知道学了有什么用。场景1:股票价格跨度— 证券交易系统中,计算股票今日价格能向前追溯多少天(连续不高于今日的天数),用单调栈O(1)时间更新每日跨度,实时监控价格趋势场景2:浏览器历史记录— 实现查找上一个访问时间更早的特定类型页面,用单调栈维护访问时间戳,快速定位相关页面场景3:性能监控— 服务器监控系统中,找出每次响应时间异常后,多久才恢复正常,用单调栈记录异常时间点,计算恢复间隔场景4:建筑物视野问题— 城市规划中,计算从某建筑向东看,第一个能挡住视线的高楼在多远处,单调栈维护高度信息,O(n)求解所有建筑视野️ 举一反三完成本课后,试试这些同类题目来巩固知识:题目难度相关知识点提示LeetCode 496. 下一个更大元素 IEasy单调栈基础和本题几乎相同,先在nums2中建立映射LeetCode 503. 下一个更大元素 IIMedium单调栈循环数组遍历两遍,用 i % n 处理循环LeetCode 84. 柱状图中最大的矩形Hard单调栈经典应用找每个柱子左右第一个更矮的,计算矩形面积LeetCode 42. 接雨水Hard单调栈/双指针单调栈找左右边界,或用对撞指针LeetCode 901. 股票价格跨度Medium单调栈实时查询维护价格递减栈,每次查询O(1)均摊 课后小测试试这道变体题,不要看答案,自己先想5分钟!题目:给定数组 nums,返回一个数组 answer,其中 answer[i] 表示 nums[i] 右边第一个大于等于它的2倍的元素的索引,如果不存在则为-1。例如:nums [2,4,1,3,6],输出 [1,4,-1,4,-1]nums[0]2,右边第一个≥4的是nums[1]4,输出1nums[1]4,右边第一个≥8的是nums[4]6(68,继续找,没有了),实际是nums[4]6(6≥8不对),没有,应该是-1… 等等,让我重新理解更正题目:nums [2,4,1,3,6],answer[i] 是右边第一个 ≥ nums[i]*2 的元素索引nums[0]2,找≥4的第一个:nums[1]4,答案是索引1nums[1]4,找≥8的:没有,答案是-1nums[2]1,找≥2的:nums[3]3,答案是索引3nums[3]3,找≥6的:nums[4]6,答案是索引4nums[4]6,找≥12的:没有,答案是-1输出:[1,-1,3,4,-1] 提示(实在想不出来再点开)还是用单调递减栈,只是弹出条件变成nums[i] 2 * nums[stack[-1]]✅ 参考答案defnextGreaterDouble(nums):单调栈变体 — 找右边第一个≥2倍的元素索引nlen(nums)answer[-1]*n stack[]foriinrange(n):# 当前元素 栈顶的2倍时,栈顶找到了答案whilestackandnums[i]2*nums[stack[-1]]:prev_indexstack.pop()answer[prev_index]i# 记录索引而不是值stack.append(i)returnanswer# 测试print(nextGreaterDouble([2,4,1,3,6]))# 输出:[1,-1,3,4,-1]核心思路:和每日温度完全一样的单调栈框架,只是弹出条件从更大变成≥2倍。这体现了单调栈模板的通用性:只要是找右边第一个满足某条件的元素,都可以用这个模式! 恭喜完成第35课!你已经掌握了单调栈这个强大的工具,它将在后续的Hard题中大显身手。记住核心思想:维护栈内单调性,遇到破坏单调性的元素时处理栈顶。下一课我们将挑战单调栈的终极应用——柱状图中最大矩形!如果这篇内容对你有帮助推荐收藏 AI Compasshttps://github.com/tingaicompass/AI-Compass更多系统化题解、编程基础和 AI 学习资料都在这里后续复习和拓展会更省时间。