每日温度问题与单调栈：从暴力破解到O(n)优化

刷题刷到一定量之后你会发现一个规律一道题之所以经典往往不是因为难而是在一个很小的切口里塞进了数据结构最核心的思想。LeetCode 739 每日温度Daily Temperatures就是这么一道题。它表面上让你算每一天要等几天才能遇到更热的天气但真正考的是你对单调栈Monotonic Stack的理解和运用。我刷这道题的时候前后用了三种解法从暴力到单调栈从右到左再到左到右每一步都踩过坑。这篇文章就把我完整的思考过程、代码实现、手动模拟和踩坑记录都摊开来讲清楚不管你是一刷的小白还是想复习单调栈的老手都能从中拿到点东西。先交代一下我写这篇文章的背景这几天在做 LeetCode 热门 100 题的过程中刚好把 739 和几个同类问题比如 496 下一个更大元素、42 接雨水、84 柱状图中最大的矩形放在一起复盘发现很多人的问题不是看不懂单调栈解法而是不知道自己为什么需要单调栈。所以这篇文章的重点不只是给你代码而是把从暴力到优化的每一步推导逻辑掰开揉碎。1. 题面拆解与暴力思路先确保看懂题目再谈优化1.1 题目到底在问什么原题描述很简短给定一个整数数组temperatures数组的长度为n其中temperatures[i]表示第i天的气温。你需要返回一个数组answer其中answer[i]表示从第i天开始要等到第几天才能遇到一个比当前天更高的气温。如果之后一直不存在更高的气温则answer[i] 0。注意一个细节答案是天数差不是温度差。比如第3天的温度是71第5天的温度是72那么answer[3]应该是2因为第 5 天在 2 天后而不是温度差1。这个理解一错后面全错。官方给出的例子是temperatures [73, 74, 75, 71, 69, 72, 76, 73] answer [1, 1, 4, 2, 1, 1, 0, 0]手动验证一下第0天是73第1天是74所以等1天第2天是75要到第6天的76才算更高所以等了4天第6天是76之后没有比76更高的温度记为0。这里最容易被忽略的是连续相等温度的情况比如[70, 70, 71]中第0天和第1天的温度都是70等更高的温度都要到第2天所以答案应该是[2, 1, 0]而不是[1, 1, 0]。这个相等不算更高的约束正是后面单调栈代码里等号判断的关键。1.2 暴力解法能过测试吗暴力解法是人的第一直觉对每一天向后扫描找到第一个比它大的温度记录距离。代码很简洁class Solution: def dailyTemperatures(self, temperatures: List[int]) - List[int]: n len(temperatures) ans [0] * n for i in range(n): for j in range(i 1, n): if temperatures[j] temperatures[i]: ans[i] j - i break return ans这个解法的时间复杂度是 O(n^2)空间复杂度是 O(1)不算返回数组的话。在 LeetCode 上n的上限是10^5所以最坏情况下10^10次比较超时是必然的。有意思的是如果你用的是 Java 或 C在部分测试数据偏随机的情况下这个暴力解法可能会擦边通过一部分测试点因为随机数据中下一个更大温度往往很快就能找到实际比较次数远小于 n^2。但这是典型的碰运气一旦测试数据被构造为递减序列比如[100, 99, 98, ..., 1]每一轮都要扫到末尾才知道后面没有更高的温度暴力解法就会彻底暴露出它的劣势。1.3 暴力解法暴露出的核心矛盾暴力解法慢在什么地方仔细想一下对于温度序列[75, 74, 73, 72, 71, 76]这种场景当我在计算第0天的答案时我会依次检查第1, 2, 3, 4, 5天最后在第5天找到76。而当我计算第1天的答案时我又会从第2天开始依次往后扫同样在第5天找到76。也就是说76这个信息被重复访问了好几次。这个问题的本质是序列中后面的高温信息本可以被后面的天数共享但暴力法里每个位置都在孤立地重新发现它。这就给了我们一个优化的方向能不能把右侧已经扫描过的温度信息用一种合理的方式缓存下来让后续计算直接复用如果能做到每个元素只需要被处理有限的次数总体复杂度就能从 O(n^2) 降到 O(n)。顺着这个思路栈这个数据结构自然就浮出水面了。2. 为什么需要单调栈从缓存右侧信息到一次遍历的思维跳跃2.1 什么信息值得缓存回到刚才的例子假设我从右往左处理数组。当我处理到第5天温度76时我已经知道了第6, 7, 8...天的情况。如果我想知道第5天之后哪一天比第4天温度72更热那么我是不是只需要看第5天及之后的候选位置关键问题来了哪些日子值得作为候选保留下来举个具体的场景假设右侧的温度依次是[75, 71, 72]。如果我现在想知道左侧某个温度更低的天气需要等几天才能升温那么候选集合里71其实是一个无效信息。因为71后面紧跟着72而72比71更高且距离更近。对于任何左侧温度如果连71都不能满足更高的要求那么72更有可能在更近的位置满足要求反过来如果左侧温度比72低那么它要么直接遇到72要么在此之前遇到比72更高的温度无论哪种情况71都不会成为第一个更高温度的答案。再换一个更直白的说法候选集合里的温度必须保持单调递减从栈底到栈顶越来越小。如果新来的温度比栈顶元素更大或相等说明栈顶这些更小或相等的温度已经没有资格继续当候选者了因为它们距离更远、温度还更低任何左端的温度在找下一个更高时都不会优先选它们。2.2 用生活类比理解单调递减栈你可以把这个过程想象成排队报数。一组人从右往左站成一排每个人只记住自己左边那群人里身高最高、位置最近的那个人。我手里维护着一个从高到低的候选队列最高的人在队首最矮的人在队尾。每当一个新的人加入队列所有身高不超过他的人都得从队尾离开因为他不只比他们更高还站得更靠左也就是更靠近未来的计算位置。这个类比直接解释了单调栈的核心操作新元素入栈前先弹出所有不大于它的栈顶元素。注意是不大于等于也要弹。因为题目要求的是严格更高的温度等于的情况下栈里那个等高的元素既不会成为答案也会挡住后面更高温度的位置信息留着它只会让栈里的单调性被破坏。这个点我在后面易错点部分会详细展开因为它真的很容易写错。2.3 为什么每个元素最多进出栈各一次单调栈复杂度为 O(n) 的底气就在这里在整个遍历过程中每个数组下标最多被压入栈一次也最多被弹出栈一次。弹出去就不再回头因为一旦某个元素被弹出说明右侧或左侧已经出现了一个比它更大/更小且更近的元素它再也不可能成为第一个更XX的答案了。这种淘汰制保证了总操作次数是 O(n)而不是 O(n^2)。这也是单调栈和暴力法最本质的区别暴力法里每个元素都可能被重复扫描很多次单调栈里每个元素只被看见两次——入栈一次出栈一次。很多初学者不理解这个复杂度分析总担心 while 循环里会不会造成多次遍历实际上由于淘汰机制的存在所有 while 循环累计执行的次数不超过 n 次。3. 从右向左扫描单调递减栈的完整推导与手写模拟3.1 算法流程与代码从右向左遍历的思路形象地说就是回头看不回头。我们从数组的最后一个元素开始倒着往前处理。遍历过程中维护一个栈栈里存的是温度数组的下标而不是温度值本身。为什么存下标因为我们要返回的是天数差存下标才能直接计算i与stack[-1]之间的距离如果只存温度值最后还得再找一遍位置得不偿失。对于当前下标i我们执行以下操作如果栈不为空且temperatures[stack[-1]] temperatures[i]说明栈顶的温度不比当前温度高。这时栈顶这个下标不可能是当前i的答案也不可能是更左侧任何下标的答案因此弹出它。重复步骤 1直到栈为空或者栈顶温度严格大于当前温度。如果栈不为空那么stack[-1]就是当前i右侧第一个温度更高的位置答案为stack[-1] - i。将i压入栈。代码如下class Solution: def dailyTemperatures(self, temperatures: List[int]) - List[int]: n len(temperatures) ans [0] * n stack [] for i in range(n - 1, -1, -1): while stack and temperatures[stack[-1]] temperatures[i]: stack.pop() if stack: ans[i] stack[-1] - i stack.append(i) return ans这个实现在 LeetCode 上可以稳定击败 90% 以上的提交。它看起来很短但每一行背后都有刚才讲过的淘汰逻辑撑着。3.2 用手算模拟一个完整例子用官方例子[73, 74, 75, 71, 69, 72, 76, 73]下标从0到7。我们倒着遍历i 7温度73。栈为空ans[7] 0入栈栈变为[7]。i 6温度76。栈顶下标7的温度是7373 76弹出。栈为空ans[6] 0入栈栈变为[6]。i 5温度72。栈顶下标6的温度是7676 72不弹。栈不为空ans[5] 6 - 5 1入栈栈变为[6, 5]。i 4温度69。栈顶下标5的温度是7272 69不弹。ans[4] 5 - 4 1入栈栈变为[6, 5, 4]。i 3温度71。栈顶下标4的温度是6969 71弹出。新的栈顶下标5的温度是7272 71停止。ans[3] 5 - 3 2入栈栈变为[6, 5, 3]。i 2温度75。栈顶下标3的温度是7171 75弹出。栈顶下标5的温度是7272 75弹出。栈顶下标6的温度是7676 75停止。ans[2] 6 - 2 4入栈栈变为[6, 2]。i 1温度74。栈顶下标2的温度是7575 74不弹。ans[1] 2 - 1 1入栈栈变为[6, 2, 1]。i 0温度73。栈顶下标1的温度是7474 73不弹。ans[0] 1 - 0 1入栈栈变为[6, 2, 1, 0]。最终结果[1, 1, 4, 2, 1, 1, 0, 0]完全正确。注意观察栈的变化从栈底到栈顶温度严格递减。栈底 - 76, 栈顶 - 73而且越靠近栈顶的位置越靠右。这就是候选集合的维护过程。3.3 三个关键疑问的解答第一个疑问为什么相等温度也要弹出比如温度[73, 73, 74]处理下标1温度73时栈里有下标2温度74不需要弹。处理下标0时栈顶是下标1温度同为73。如果条件写成while stack and temperatures[stack[-1]] temperatures[i]那么下标1不会被弹出ans[0]会被计算为1 - 0 1这显然是错的因为第1天的温度和第0天一样并没有更高正确答案应该是2。所以必须用把相等的温度从候选列表里淘汰掉。第二个疑问为什么答案初始化为0就行因为如果某个下标最终没找到更大的温度栈为空时我们什么也不做ans[i]保持初始值0正好符合题目要求。这个设计很精巧也省去了一次显式的赋值。第三个疑问为什么栈不存温度值而是存下标这是为了算天数差。其实也有变体题目只问下一个更大元素的值那种题目不存下标存数值也能做但每日温度这道题必须用下标因为ans数组要的是距离。存下标还有一个额外好处通过temperatures[stack[-1]]我们可以随时拿到温度值信息没有丢失而下标本身又能用来计算距离一举两得。4. 从左向右扫描出栈时刻记录答案的另一视角4.1 思路转换让每个位置在出栈时被回答从右向左的做法是站在每个当前位置向前看栈里准备好的候选。还有一种常见的写法是从左向右遍历思路更符合直觉当我们在遍历过程中遇到一个新的温度temperatures[i]时它有机会成为栈中尚未找到答案的温度的第一个更高温度。也就是说答案在被出栈的那一刻被记录下来。具体流程从左向右遍历栈中存下标栈底到栈顶的温度单调递减同样要求严格递减。当遍历到temperatures[i]时如果栈不为空且temperatures[stack[-1]] temperatures[i]说明当前这个新温度是栈顶下标的答案。弹出栈顶idx令ans[idx] i - idx。重复步骤 2直到栈为空或者栈顶温度不小于当前温度。将i入栈。这里要注意出栈条件变成了严格小于不是。两个方向的等号处理恰好相反反应的是候选淘汰和答案结算两个不同时刻的语义。对应代码class Solution: def dailyTemperatures(self, temperatures: List[int]) - List[int]: n len(temperatures) ans [0] * n stack [] for i in range(n): while stack and temperatures[i] temperatures[stack[-1]]: idx stack.pop() ans[idx] i - idx stack.append(i) return ans4.2 从左向右的模拟过程还是用[73, 74, 75, 71, 69, 72, 76, 73]i 0温度73。栈为空入栈栈变为[0]。i 1温度74。74 73弹出下标0ans[0] 1 - 0 1。入栈栈变为[1]。i 2温度75。75 74弹出下标1ans[1] 1。入栈栈变为[2]。i 3温度71。71 75不弹出。入栈栈变为[2, 3]。i 4温度69。69 71不弹出。入栈栈变为[2, 3, 4]。i 5温度72。72 69弹出下标4ans[4] 1。72 71弹出下标3ans[3] 2。72 75停止。入栈栈变为[2, 5]。i 6温度76。76 72弹出下标5ans[5] 1。76 75弹出下标2ans[2] 4。栈为空。入栈栈变为[6]。i 7温度73。73 76不弹出。入栈栈变为[6, 7]。结果同样是[1, 1, 4, 2, 1, 1, 0, 0]。可以看到从左向右的写法里答案在下标出栈时被结算所以那些始终没有出栈的下标比如6和7保持初始值0。4.3 两种写法的比较谁更好对比维度从右向左从左向右栈的语义当前下标右侧的候选位置尚未找到答案的历史位置答案记录时机当前下标入栈前记录历史下标出栈时记录弹出条件弹出温度不高于当前值的弹出温度低于当前值的直觉难度需要想清楚右侧信息的维护更符合遇到更大就结算的直觉代码长度约 6 行约 6 行等号处理弹出相等不弹出相等从我个人的经验看两种写法没有绝对的优劣。从右向左的代码在找下一个更大元素这类问题里更统一因为换题时不太容易把和搞混从左向右则更贴近结算思维适合初学者建立出栈即答案的直觉。但前提是你必须清楚等号的差异否则左思右想也调不对。建议两个版本都自己写一遍然后固定其中一种作为主力模板。一个值得提的细节是栈中的温度始终是单调递减的——两种写法都成立。这是单调栈这类问题最大的特征无论遍历方向如何栈里存放的候选集合都维持一种有序性正是这个有序性让淘汰变得高效。5. 单调栈为什么是对的复杂度下界与同类问题的通用识别法5.1 理论上的正确性为什么弹出的元素不再需要严格地说单调栈算法依赖一个核心论断当栈顶元素t被当前元素x弹出时x就是t右侧或左侧第一个大于t的温度。为什么因为栈中的元素是按位置顺序依次入栈的如果t在栈顶还没有出栈说明在t入栈之后我们还没有遇到一个比它更大的元素否则它早就被弹出了。因此遍历到x时x是自t之后遇到的第一个严格大于t的元素。这就是答案的正确性来源。从另一个角度看栈顶被弹出的元素它的生命周期结束了——在它入栈到出栈之间它一直在等一个更大的元素而现在它等到了。出栈的那一刻答案被确定。右往左的写法本质相同只是把等换成了查。5.2 为什么 O(n) 是最优的很多人会问能不能比 O(n) 更快答案是不能。因为输出的ans数组本身有n个元素光是把结果写出来就需要 O(n)。在比较模型下每个位置至少要知道它右侧第一个比它大的位置最坏情况下即使输入已经排序好我们也得检验每一个位置是否有后继。所以 O(n) 就是理论下界单调栈已经做到最优了。5.3 如何一眼识别可以用单调栈的题目根据我做题的经验这类题目通常有以下特征题目要求下一个更大的元素、下一个更小的元素、左边第一个比它大/小的位置。输入是一个一维序列且答案与第一个这个限定词有关。暴力解法是明显的 O(n^2)而且瓶颈在于反复扫描同样的信息。常见的同类题目包括LeetCode 496下一个更大元素 I。LeetCode 503下一个更大元素 II环形数组版处理方式是把数组遍历两遍。LeetCode 42接雨水利用递减栈维护凹槽。LeetCode 84柱状图中最大的矩形利用递增栈维护边界。这些题的核心思路可以互相迁移。比如 503 环形数组版做法就是遍历2n个位置下标对n取模其余逻辑几乎一样。掌握了 739这道环形变体基本是白送。还有一个很实用的经验遇到找下一个更大的题目先问自己能不能从右向左遍历维护一个候选栈然后立刻用单调栈来写。如果题目改成找下一个更小只需要把弹出条件里的改成或把改成逻辑完全对称。这也是为什么我强烈建议你花一个晚上把 739、496、503 三道题连刷的原因因为它们本质上就是一个模板的三种形态。6. 高频易错点与调试实战从 WA 到 AC 的完整链路6.1 等号的取舍是最大的坑我前面反复强调等号问题这里展开说说。在从右向左的解法里弹出条件必须是temperatures[stack[-1]] temperatures[i]。如果你写成遇到相等温度时就会判断错误。举一个极端的测试用例temperatures [73, 73, 73]。正确答案是[0, 0, 0]因为没有任何一天之后有严格更高的温度。但如果你用写成从右向左的版本i 2入栈。i 1温度73栈顶也是7373 73为假不弹出ans[1] 1。i 0栈顶为1ans[0] 1。输出变成[1, 1, 0]错得离谱。而在从左向右版本里弹出条件必须写成temperatures[i] temperatures[stack[-1]]即严格大于才结算这样才能保证相等温度不会误判。总结成一句话向右看时相等温度不能算数向左看时相等温度必须被淘汰。方向不同等号处理相反我建议你在代码旁边注释清楚这里为什么用 / 防止过两天自己都忘了。6.2 下标越界与空栈判断另一个常见错误是在 while 循环里直接访问栈顶而不判空。Python 里stack[-1]在栈为空时会抛出IndexError所以 while 循环条件一定要先判断stack。很多初学者写出的代码长这样# 错误示范 for i in range(n - 1, -1, -1): while temperatures[stack[-1]] temperatures[i]: # 空栈时崩溃 stack.pop()正确写法是while stack and temperatures[stack[-1]] temperatures[i]。注意 Python 的and是短路求值先判断stack非空才会取stack[-1]所以顺序不能反。6.3 调试技巧小样例手动模拟与随机对拍如果提交后出现 WA错误答案我的调试思路一般是这样第一步造一个包含相等温度、严格递增、严格递减、先降后升等情况的短测试用例手动模拟一遍。比如[73, 74, 75, 71, 69, 72, 76, 73] # 官方样例 [30, 40, 50, 60] # 严格递增 [1, 1, 1, 0] [60, 50, 40, 30] # 严格递减 [0, 0, 0, 0] [30, 30, 30] # 全相等 [0, 0, 0]第二步在本地用 Python 写一个暴力解法和一个随机数组生成器然后用for循环做几百轮对拍import random def brute(temperatures): n len(temperatures) ans [0] * n for i in range(n): for j in range(i 1, n): if temperatures[j] temperatures[i]: ans[i] j - i break return ans def monotonic(temperatures): n len(temperatures) ans [0] * n stack [] for i in range(n - 1, -1, -1): while stack and temperatures[stack[-1]] temperatures[i]: stack.pop() if stack: ans[i] stack[-1] - i stack.append(i) return ans for _ in range(1000): arr [random.randint(1, 100) for _ in range(random.randint(1, 20))] if brute(arr) ! monotonic(arr): print(Mismatch:, arr) break这个对拍脚本几乎每次都能帮我快速定位错误比对着 LeetCode 的报错信息猜要高效得多。你能在本地跑通对拍再把代码贴到 LeetCode 上基本就是一次 AC。6.4 性能对比一次本地实验的实测数据我在本地做了一次简单测试对n 10^5长度的随机数组分别运行暴力解法和单调栈解法。暴力解法跑了约 1.8 秒单调栈解法约 0.03 秒差距接近 60 倍。如果把数据换成递减序列暴力解法直接跑到几十秒都跑不完单调栈依然是稳定在个位数毫秒级别。所以从这个题目开始算法复杂度决定成败这件事就有非常直观的体感了。7. 从刷题到业务每日温度的实际映射与同类必刷清单7.1 这道题在真实业务里的样子很多人会问LeetCode 上的题目到底有什么用每日温度这类题对应的抽象能力是在一维时间序列中为每一个事件找到它之后第一次满足某个条件的事件位置。这个模式在实际业务中出现的频率比你想象的高。举几个例子股票行情系统给定每日收盘价计算每个交易日距离下一个更高收盘价的天数。这个指标在技术分析里叫未来回报周期可用于回测中判断买点后的最短上涨时间。监控告警系统一组服务器每 5 分钟上报一次 CPU 使用率需要找到每次告警后第一次恢复正常的时刻。抽象一下就是下一个低于阈值的元素位置正好是最小值版的单调栈。传感器数据处理工业设备每分钟记录一次温度当某次温度超过警戒线后需要预测下一次达到更高峰的时间窗口。这就是把每日温度里的温度换成传感器读数。这些场景共同点是输入是流式或批量的一维数组输出是距离最近的一个满足条件的位置差。只要抓住这个抽象你在系统设计阶段就能意识到应该用单调栈而不是双层循环尤其是在数据量达到十万、百万级别时。7.2 我的必刷清单与刷题顺序如果你正在刷 LeetCode 热门 100 题或者冲着面试准备单调栈专题我建议按这个顺序来LeetCode 739每日温度——入门理解单调栈解决下一个更大/更小元素的基本模板。LeetCode 496下一个更大元素 I——把下一个更大应用到两个数组之间的映射。LeetCode 503下一个更大元素 II——环形数组变体加一个遍历 2n 次的技巧。LeetCode 84柱状图中最大的矩形——单调栈的进阶应用难点在于理解左右边界如何用栈来维护。LeetCode 42接雨水——把单调栈和面积累计结合起来成就感很强。如果你时间紧张我会建议 739 84 的组合优先过一遍因为 739 建立模板84 建立边界思维这两个能力在面试中非常实用。另外LeetCode 994腐烂的橘子虽然不涉及单调栈但它是 BFS 的经典入门适合放在同一个图搜索专题里一并刷掉。如果你在准备周赛或笔试可以把基本计算器这类栈混合运算的题也排到后面它们考察的是同一套数据结构在不同语义下的应用。7.3 从一道题到一类题刷题效率的复利效应我个人最大的体会是刷题不要追求每题都从零开始思考而是要刻意建立题型模板。当你把 739 吃透时你会发现 496、503 都是换皮不换里当你把 84 吃透时你会开始理解单调栈栈底到栈顶的有序性到底在维护什么几何意义。这种认识的迁移能力才是刷题数量之外最值钱的东西。具体到每日温度这道题我希望你合上这篇文章后能自己完成三件事第一不加任何提示写出从右向左的单调栈解法并讲清楚为什么用第二用刚才的对拍脚本验证代码正确性第三自己改一版下一个更小元素的解法看看需要把哪些符号翻转。这三步做完这道题才算真正吃透了。最后再分享一个小技巧我现在会把单调栈这类题总结成一个统一的思考模板——先问每个元素的答案在入栈前结算还是出栈时结算再问栈内单调性的方向是什么最后问相等元素如何处理。只要这三问能答清楚代码基本不会写错。希望这个思路也能帮你少走一些弯路。