LeetCode 739「每日温度」是我这几年给学弟学妹推荐频率最高的一道单调栈入门题。经常有朋友刷到它一看题干就笑了给一个每天温度的数组返回一个新数组每个位置要写的是“下一次出现更高温度要等几天”等不到就写0。就这么一个看似平平无奇的题现在挂在 LeetCode 热门 100 题里面试出镜率极高而且周赛里很多压轴题的做法追根溯源都能回到这题。我第一次刷它用的是暴力两层循环AC 之后沾沾自喜直到某次模拟面试被追问“为什么暴力不能过、怎么压到 O(n)”才意识到这题真正值钱的不是那个 Accepted而是从暴力到单调栈的完整推导过程。这篇文章就把这个过程掰开揉碎讲清楚。1. 读题解法先别急着写代码把“等待天数”翻译成下标差1.1 从“等几天”到“下标相减”先说人话。temperatures[i] 是第 i 天的温度我们要找的是 j i使得 temperatures[j] temperatures[i]并且 j 是满足条件的最靠前的一个。答案就填 j - i不是温度差值也不是 j 本身这点是新手最容易踩的第一个坑。举个例子温度数组是 [73, 74, 75, 71, 69, 72, 76, 73]位置 2 是 75向右看下一个严格大于 75 的温度是位置 6 的 76所以要等 6 - 2 4 天。注意中间虽然有 71、69、72它们都比 75 小不影响答案。如果中间出现相等的温度也不能算必须严格大于比如 [75, 75, 76] 里第 0 个 75 要等 2 天而不是 1 天。还有最后一类位置比如数组末尾那天的温度它后面没有任何日子了答案直接是 0。哪怕某个位置后面温度一直降永远等不到更高温度答案也写 0。题目默认了输入数组长度至少为 1所以不用处理空数组但实际工程里顺手判一下也行。1.2 暴力解法是什么水平O(n^2) 为什么扛不住暴力解法不用动脑对每个 i从 i1 开始往后扫找到第一个大于 temperatures[i] 的位置就停下来填答案。代码如下def dailyTemperatures_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逻辑完全正确但复杂度是 O(n^2)。为什么说扛不住题目给的 n 最大能到 10^5最坏情况下比如温度单调递减[100, 99, 98, ..., 1]对每个 i 都得把后面全部元素扫完才发现没有更高温度总操作次数接近 n(n-1)/2也就是 10^10 这个量级。就算机器每秒能跑 10^8 次简单操作也要一百多秒早超时了。不过暴力不是一无是处。我强烈建议别删掉它平时调试用暴力版和单调栈版对拍随机生成几百组数据比对结果能帮你快速验证优化版写没写错。这个习惯在刷所有“从暴力优化到高效解”的题时都受用。2. 核心思路单调栈是怎么把 O(n^2) 压到 O(n) 的2.1 为什么“栈”能解决右侧更高温度问题先想一个生活场景一群人从前往后排成一列每个人都在等身后第一个比自己高的人出现。如果排队时来了一个个子很高的人他可能一口气让前面好几个人“等到答案”因为他是这些人共同遇到的第一个更高的人。这个“先拦住最近的人再往后结算”的过程天然就适合栈栈里存的是还没等到答案的人新来的人从栈顶开始挨个跟旧人比身高比他矮的旧人可以结算离场比他高的旧人则继续等着。放到本题里栈里存的不是温度值而是日期的下标。为什么要存下标因为答案要的是天数差存下标才能算出 j - i。如果只存温度值你还得额外记录它出现在哪一天等于自己给自己挖坑。从左往右扫描的同时维护一个栈保持栈里下标对应的温度是严格递减的从栈底到栈顶温度越来越低。换句话说栈顶永远是目前还没找到答案的日子里温度最低的那天。新来一天的温度如果比栈顶温度高说明栈顶那天的答案等到了弹出并填结果继续看新的栈顶直到栈空或者栈顶温度不小于当前温度再把当前下标压栈。2.2 从左往右写法弹出时结算答案直接给出标准实现def dailyTemperatures(temperatures): n len(temperatures) ans [0] * n stack [] for i in range(n): while stack and temperatures[i] temperatures[stack[-1]]: j stack.pop() ans[j] i - j stack.append(i) return ans这个版本大概是我见过最短的单调栈代码之一。关键就一句话当前温度把栈顶元素比下去时当前天就是栈顶元素等到的第一个更高温度日。因为栈顶元素是一直没找到答案的我们从左往右扫描当前天是它第一次遇到的比自己高的天所以答案就是当前下标减去它的下标。有人会问那栈里其他元素呢比如栈底温度很高当前温度比它低它暂时不用结算继续等着。等以后有一天温度高到能盖过它当时扫描到的那个下标就是它的答案。每个元素最多入栈一次、出栈一次所以总复杂度 O(n)。这题立刻从 10^10 级别的运算变成了 10^5 级别差距就是这么大。2.3 从右往左写法先知道未来信息再去匹配过去另一种常见实现是从右往左扫。它的思路是我先把自己右边的“候选日”组织好然后对于当前天在候选里找第一个温度更高的。代码长这样def dailyTemperatures(temperatures): n len(temperatures) ans [0] * n stack [] for i in range(n - 1, -1, -1): while stack and temperatures[i] temperatures[stack[-1]]: stack.pop() if stack: ans[i] stack[-1] - i stack.append(i) return ans从右往左时栈里维护的是右侧候选下标的序列越靠近栈顶下标离当前越近。每次把栈顶温度小于等于当前温度的弹出因为当前温度更高且更靠左那些被弹出的日子不可能再成为更左边任何天的“下一个更高温度”了——左边那些天如果要找更高温度会先撞到当前天。弹完之后栈顶剩下的就是右边第一个比当前温度高的位置填答案即可。两种写法面试官都认但我个人更推荐你先练第一种。原因很朴素第一种的思维链条是“新来的人帮旧人结算”每一步弹出的原因很直观出错的概率低第二种需要主动淘汰无用候选刚接触单调栈时容易写出边界 bug。等到第一种写顺手了再回头看第二种你会对“单调栈到底在维护什么”有更深的理解。3. 实操细节与排查技巧从 AC 到面试稳3.1 用真实数据推演一遍完整流程拿 LeetCode 官方示例 temperatures [73, 74, 75, 71, 69, 72, 76, 73] 走一遍从左往右的单调栈i0温度 73栈空入栈栈[0]i1温度 74大于栈顶 0 号位的 73弹出 0ans[0]1-01入栈 1栈[1]i2温度 75大于栈顶 1 号位的 74弹出 1ans[1]2-11入栈 2栈[2]i3温度 71小于 75入栈 3栈[2, 3]i4温度 69小于 71入栈 4栈[2, 3, 4]i5温度 72大于栈顶 4 号位的 69弹出 4ans[4]5-41继续比较72 大于栈顶 3 号位的 71弹出 3ans[3]5-3272 小于栈顶 2 号位的 75停止入栈 5栈[2, 5]i6温度 76大于栈顶 5 号位的 72弹出 5ans[5]6-5176 大于栈顶 2 号位的 75弹出 2ans[2]6-24栈空入栈 6栈[6]i7温度 73小于 76入栈 7栈[6, 7]最终答案 [1, 1, 4, 2, 1, 1, 0, 0]和题目输出一致。细看这个推演过程你会发现每个元素确实只入栈出栈一次比如 75 在第 6 天才弹出是因为它一直等到 76 才看到第一个更高的温度中间那些 71、69、72 都比它小压根没资格触发它的结算。3.2 边界用例自测清单写完之后别急着交我习惯用下面这组用例快速自测几乎能覆盖所有坑输入预期输出说明[30][0]只有一个元素没有未来天数[30, 31, 32][1, 1, 0]严格递增最后一天永远 0[32, 31, 30][0, 0, 0]严格递减所有位置都等不到更高温度[30, 30, 31][2, 1, 0]相等温度不结算必须严格大于[31, 30, 30, 32][3, 1, 1, 0]等值位置要跨过前面的相等日特别是最后两组专门用来检查你没把“大于等于”和“大于”搞混。从左往右写法里弹出条件是 temperatures[i] temperatures[stack[-1]]是严格大于如果你写成 等于的情况也会结算答案就会偏小。从右往左写法里弹出条件是 temperatures[i] temperatures[stack[-1]]这里反而是要带上等于的因为它要淘汰“不可能成为更优候选”的相同温度日子两个方向刚好相反很多人写反了还不自知。3.3 面试追问复杂度分析与 O(1) 空间进阶做完基础 AC面试官大概率补一句“时间复杂度是多少为什么”。答案分两层第一层每个下标最多入栈一次、出栈一次入栈出栈都是 O(1) 操作所以整体 O(n)第二层这就是均摊分析的感觉虽然 while 循环可能连续弹出多个元素但所有 while 加起来的总弹出次数不会超过 n。更狠的追问是这个能不能把额外空间压到 O(1)。普通单调栈的空间是 O(n)但本题里温度范围很特殊是华氏 30 到 100一共就 71 个取值所以可以开一个固定大小的数组当“温度到最近出现下标的映射”。从右往左扫描实时更新每个温度最近出现的位置然后对于当前温度 t去看 t1 到 100 这些温度里谁在右侧出现得最早取最近的那个位置减当前下标即可def dailyTemperatures_constant_space(temperatures): n len(temperatures) ans [0] * n last_pos [n] * 101 # 温度范围 30~100初始化为 n 表示还没出现 for i in range(n - 1, -1, -1): t temperatures[i] nearest n for higher in range(t 1, 101): nearest min(nearest, last_pos[higher]) if nearest n: ans[i] nearest - i last_pos[t] i return ans这段代码看着朴素但它展示了“数据范围本身也是优化条件”的思维。温度上限是固定的 100所以内部那层循环最多跑 70 次可以理解为常数空间上只有固定 101 长度的数组严格说是 O(1)。面试如果能把这一层讲出来比单纯背模板的人强很多。3.4 我见过的常见错误速查表最后把实际写题时会犯的错误集中列一下错误类型错误写法正确做法栈里存温度值stack.append(temperatures[i]) 然后回头找下标栈里存下标温度用 temperatures[stack[-1]] 取答案填成下标ans[j] i 而不是 i - j天数差是下标差不是目标下标弹出条件用错从左往右写成 从左往右严格大于才结算忘记初始化答案ans 全 0栈里最后剩下的元素没处理初始化 ans 全 0栈里剩余的天然保持 0从右往左时栈剩余判断缺失直接 stack[-1] 导致越界先判断 if stack前三个错误我都在不同时期犯过尤其是“存值不存下标”一错就是结构性错误改起来比存下标麻烦得多。建议新手第一次写的时候先在注释里标明栈的类型是 List[int]里面是下标不是温度能有效减少潜意识把值塞进去的冲动。4. 同类题串讲739 刷完之后这些题可以接着上4.1 单调栈题型的两种骨架739 刷熟之后你会发现单调栈在 LeetCode 里基本分成两路。第一路是“下一个更大/更小元素”系列核心模式和 739 几乎一样维护一个栈新元素触发弹出时结算答案区别只是方向、严格性、答案存的是距离还是元素值。第二路是“柱状图/接雨水”这类贡献面积题栈里弹出一个元素时除了要知道它等到了谁还要算左右边界夹出来的宽度或面积单调栈里“弹出即结算”的思想直接复用。搞清楚自己刷的题属于哪一路比盲目背代码重要。739 是第一路的经典代表所以你会看到很多博客把它和 496、503、901 放在一起讲等你要挑战 84、42 时又会有专门讲第二路的文章提到 739说它是那道题的“前置铺垫”。这也是我推荐它作为入门题的原因——它是连接这两个分支的枢纽。4.2 496 下一个更大元素 I多了张映射表这道题给了两个数组 nums1 和 nums2nums1 是 nums2 的子集让你对 nums1 里每个元素去 nums2 里找它右侧第一个更大的元素。和 739 的区别在于739 是对整个数组的每个位置算距离而 496 只需要挑一部分元素的值所以做法是先用单调栈扫描 nums2同时用一个哈希表记录“每个值的下一个更大元素是谁”最后再遍历 nums1 查表。核心模板还是一样的从左往右扫 nums2弹出栈顶时栈顶元素的下一个更大元素就是当前元素写入哈希表。如果你把 739 的“距离”改成“值”再把结果存进哈希表代码骨架几乎不用大改这能帮你建立“模板迁移”的感觉。4.3 84 柱状图中最大矩形和 42 接雨水弹出的元素开始算面积两道题都是单调栈进阶题里的常客。84 是给一串高度找能勾勒出的最大矩形面积做法是维护单调递增栈遇到更矮的柱子时弹出并拿弹出的柱子高度乘以左右边界距离算矩形面积经常还要在数组两端补 0 当哨兵不然栈里剩下柱子没法正常结算。42 接雨水则是经典“凹槽存水”用单调递减栈维护左侧边界弹栈时计算横向宽度和高度差累加出水量。这两题代码看着比 739 复杂但你回头看它们触发弹栈的时机、用下标算宽度、弹出即结算这三件事和 739 完全是一脉相承。我的建议是刷完 739 之后趁手感还在一天之内把 496、503 这类“下一个更大元素”先刷了再拿出一天时间去啃 42 和 84效果会比孤立刷题好很多。5. 一点刷题心得最后分享几个我自己的体会。第一模板别贪多。从左往右单调栈这一个模板在 739、496、503、901 这些题里都能复用把它练到 5 分钟内能盲写出来比同时背三四种变体更靠谱。我当年就是两种写法都想掌握结果面试时反而犹豫了一下该用哪种“进度条”卡了一下。第二务必重视相等温度的处理。这个点最隐蔽也是最容易被测试用例打脸的。记住口诀从左往右严格大于才弹出从右往左大于等于就弹出。方向不同规则不同写的时候要顺手写清楚注释。第三面试被追问 O(1) 空间时别慌。温度范围这个信息是官方 follow-up 里明确提到的条件。如果你知道基于温度范围做 last_pos 映射能直接给出常数空间方案这是非常明显的加分项。就算现场没写对能把思路讲出来也比只会默写单调栈强。个人经验是这题刷三遍才算掌握第一遍暴力跑通第二遍单调栈 AC第三遍两三天后不看任何参考盲写同时写出两种遍历方向再顺手讲讲复杂度。达到这个标准之后里面对单调栈的感觉基本就是肌肉记忆了后面接雨水、最大矩形那些题你会在某个瞬间突然发现原来考点都是这题玩剩下的那套弹出结算逻辑。