做了这么多年算法题LeetCode 739这道“每日温度”题我一直把它看作单调栈的敲门砖。它不像有些题那样上来就要你背模板而是让你在“为什么维护一个递减栈就能解决问题”的推导中真正理解单调栈的本质。这篇文章就来拆解这道模板题的完整思路、两种写法的取舍以及如何把这一题的能力迁移到一系列同类题上。1. 先搞清楚题目到底在说什么场景拆解与暴力解的自然推导1.1 题目描述与输入输出约定题目给了一个整数数组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]我们来验证一下第 1 天 73°F第 2 天 74°F 就更高了所以answer[0] 1第 2 天 74°F第 3 天 75°F 更高所以answer[1] 1第 3 天 75°F一直到第 7 天 76°F 才更高中间隔了 4 天所以answer[2] 4第 6 天 72°F第 7 天 76°F 更高answer[5] 1第 7 天 76°F 之后没有更高温度answer[6] 0最后一天自然也是 0注意题目要求的是“等待的天数”不是“温度差”所以算的是下标差j - i而不是temperatures[j] - temperatures[i]。这个细节看似简单实际写代码时却经常有人算错。1.2 暴力解两层循环能过吗拿到这道题最直觉的思路就是双层循环对每个位置i往后扫描j找到第一个temperatures[j] temperatures[i]的位置记录j - i。代码如下def dailyTemperatures(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这个解法没有问题逻辑完全正确。但问题出在复杂度上最坏情况下比如数组是递减的[5,4,3,2,1]内层循环每次都要扫到结尾才发现没有更高温度。时间复杂度是 O(n²)空间复杂度是 O(1)。在 LeetCode 上temperatures的长度通常是[1, 10^5]。n² 意味着最多 10^10 次操作这个量级在 1 秒限制下基本不可能通过。所以我们必须找到更优的解法。1.3 数据范围决定了算法方向看到 n 是 10^5 这个量级你应该本能地想到目标复杂度应该是 O(n) 或 O(n log n)。而 O(n log n) 的解法比如用堆、线段树在这里其实有点杀鸡用牛刀因为这道题有一个特性——每个元素右侧第一个比它大的位置——这正好是单调栈的主场。我个人的习惯是在动手写题之前先看看数据范围再决定要不要追求最优解。如果 n 是 1000 以内暴力 O(n²) 完全可以直接交但如果 n 上限是 10^5就必须把“滑动窗口、单调栈、双指针、前缀和”这类线性或接近线性的思路在脑子里过一遍。739 这道题之所以适合当模板题就是因为它把“为什么暴力不行、单调栈为什么高效”这个矛盾暴露得特别清楚。2. 从“等多久升温”到“右边第一个更大值”单调栈的直觉来源2.1 如果把问题反过来看暴力解之所以慢是因为对每个i我们都要往后“眺望”重复扫描了很多次。现在不妨换个方向从右往左遍历。假设我们已经处理完i右边的所有元素当我们站在位置i时其实只关心右边有没有比temperatures[i]更大的温度以及第一个更大值在哪个下标。那么问题来了右边那些“比temperatures[i]小”的元素对更左边还在等着判断的候选元素来说还有没有价值假设左边还有一个位置k i它也在等下一天升温。如果温度序列在位置i处的值是temperatures[i]而它右边的某个位置j温度更低比如temperatures[j] temperatures[i]那么这个j永远不可能成为左边任何位置的“第一个更高温度”。为什么因为i在j的左边且temperatures[i] temperatures[j]。对于左边任意位置k如果它能等到j升温那它一定也会在j之前遇到i而i温度更高。所以“第一个更高温度”只会比j更早出现。换句话说我们扫描时一旦遇到一个更高的温度右侧那些更低的温度就过时了可以丢掉了。这个“丢掉过时元素”的思想就是单调栈的雏形。2.2 用排队等位的例子理解单调栈你去奶茶店排队每个人都想等到“下一杯比自己手里那杯更甜的奶茶”。如果你手里是一杯标准糖而你前面队伍里某个人手里拿的是无糖那你根本不需要关心这杯无糖——因为只要出现一杯比你甜的它一定比无糖那杯更早出现无糖对你没有任何参考价值。所以队伍里的人从队尾到队头手里的奶茶甜度必须越来越低。一旦出现一个“甜度更高的新人”所有甜度不如它的老成员都被淘汰。这个“淘汰”动作正是单调栈在弹栈。2.3 单调栈到底在维护什么单调栈里的元素从栈底到栈顶是单调递减的以本题为例指温度单调递减。我们不需要维护一个完整的“右边所有更大值列表”只需要维护一个“当前右侧候选温度的下标序列”。每来一个新位置i我们把栈顶所有温度小于等于temperatures[i]的元素弹出因为这些元素对于i左边的元素已经没有价值了。弹完之后如果栈不为空栈顶元素就是i右边第一个比temperatures[i]大的温度所在下标。维护这个单调性的代价是每个元素最多入栈一次、出栈一次。所以整体是 O(n)这是一个非常漂亮的线性算法。3. 模板代码逐行拆解为什么栈里存下标而不是存温度3.1 正序遍历的标准写法LeetCode 739 最常见的写法是正序遍历数组维护一个单调递减栈。直接上代码def dailyTemperatures(temperatures): n len(temperatures) ans [0] * n stack [] for i in range(n): # 当前温度比栈顶温度高说明栈顶元素等到了第一个更高温 while stack and temperatures[i] temperatures[stack[-1]]: prev_index stack.pop() ans[prev_index] i - prev_index stack.append(i) return ans这段代码只有几行但信息量非常大。我一行一行拆。3.2 为什么栈里存下标而不是直接存温度值这是我刚开始学单调栈时最大的一个疑问。既然比较的是温度大小直接把温度值存进栈里不行吗问题的关键在于我们要返回的答案是“等待天数”即下标差。如果栈里只存温度弹出栈顶时我们根本不知道这个温度原来对应哪个位置也就无法计算i - prev_index。所以栈里必须存下标。想要获得下标对应的温度直接用temperatures[stack[-1]]就能拿到这并不费事。所以存下标是一举两得的做法既能比较温度又能计算距离。3.3 弹栈的时机到底意味着什么while stack and temperatures[i] temperatures[stack[-1]]这个条件判断里重点是temperatures[i] temperatures[stack[-1]]。只要当前温度比栈顶温度高就说明栈顶元素等到了第一个更高温。为什么是“第一个”因为栈中维护的是从栈底到栈顶递减的温度序列。栈顶是当前还没有找到更高温度的位置中最靠右的一个。换句话说栈顶元素是所有未匹配位置中离当前位置最近的那个。当我们从右往左遍历时在正序里的表现就是从左往右处理后反过来匹配第一个被弹出的元素就是最早遇到更高温度的。每次弹出时我们记录ans[prev_index] i - prev_index这意味着栈顶元素在位置prev_index处等到了位置i的更高温度中间隔了i - prev_index天。弹完之后当前下标i本身也要入栈因为它还没找到右侧更高的温度将来它也可能成为某个左边元素的“第一个更高温度”。3.4 手动模拟一遍执行过程拿[73, 74, 75, 71, 69, 72, 76, 73]来手动跑一遍itemperatures[i]栈存下标动作073[]栈空入栈栈[0]174[0]7473弹出0ans[0]1入栈栈[1]275[1]7574弹出1ans[1]1入栈栈[2]371[2]7175不弹入栈栈[2,3]469[2,3]6971不弹入栈栈[2,3,4]572[2,3,4]7269弹出4ans[4]17271弹出3ans[3]27275停止入栈栈[2,5]676[2,5]7672弹出5ans[5]17675弹出2ans[2]4栈空入栈栈[6]773[6]7376不弹入栈栈[6,7]最终ans [1, 1, 4, 2, 1, 1, 0, 0]和题目示例完全一致。3.5 复杂度分析为什么是 O(n)直观上虽然代码里有 while 循环但每个元素只会被弹出栈一次。所有元素加起来最多入栈 n 次、出栈 n 次所以总操作次数是 O(n)而不再是 O(n²)。这一点是单调栈最迷人的地方通过维护一个带有淘汰机制的栈把每个元素被比较的次数压到常数级。这也是为什么算法面试里经常出现“看似要两层循环结果用栈把复杂度降到线性”的典型案例。4. 倒序遍历写法与两种风格的取舍4.1 倒序遍历同样能解既然正序遍历是“等到更高温度时把栈顶答案补齐”那倒序遍历则是“某个位置入栈时右侧的候选信息都已经准备好了”。倒序遍历的代码如下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这个写法的逻辑是从右往左遍历stack里存的是“已经遍历过的右侧位置”。弹出所有温度小于等于temperatures[i]的栈顶。因为右边这些温度更低的位置对于i以及更左边的位置来说都是“无效候选”。弹完之后如果栈非空栈顶就是右边第一个比temperatures[i]大的位置。把i入栈继续往左走。4.2 两种写法的对比为了方便对比我列了一张表维度正序遍历写法倒序遍历写法遍历方向从左到右从右到左弹出条件temperatures[i] temperatures[stack[-1]]temperatures[i] temperatures[stack[-1]]更新答案时机弹出时更新被弹出位置的答案入栈前直接查栈顶并更新当前答案栈内趋势从栈底到栈顶递减从栈底到栈顶递减思路理解有点“事后结算”的感觉有点“事前查询”的感觉正序的解法和“答案数组逐个被填充”这种过程很对应所以多数人觉得正序更顺手。倒序则更符合“站在当前位置看右边已经梳理好的候选序列”这一思维方式在“下一个更大元素”这类题目里也很常见。4.3 两种风格怎么选我的个人建议两种都要会写面试/做题时挑自己更熟的那种。但如果你只能记一种我建议记正序。理由是正序写法的弹栈动作和答案填充发生在同一个地方逻辑更集中。正序写法在“接雨水”“柱状图最大矩形”等后续题目里能无缝迁移因为那些题也是从左到右扫描、用递减栈维护边界信息。倒序写法在“下一个更大元素 II”循环数组这类题里会更直观一些因为循环数组需要把数组拼两倍来看倒序处理时天然方便。如果你刚开始接触单调栈我的建议是先用正序把 739 吃透等完全理解“为什么弹出时更新答案”之后再对照着写一遍倒序版本。写不出来没关系对着上面的代码抄一遍、手动模拟一遍你会发现自己对单调栈的理解立刻上升一个台阶。5. 边界条件与易错点我踩过的坑5.1 最后留在栈里的元素答案要初始化为 0正序写法里有一段代码是每轮循环开头就初始化了ans [0] * n。这个初始化至关重要因为那些“始终没有等到更高温度”的位置答案应该是 0而它们最终会留在栈里不会被任何弹出动作更新。如果你把数组初始化为[-1] * n或者不初始化最后得到的结果就会出错。记住单调栈只负责更新那些“被弹出”的位置未弹出的位置答案保持初始值。5.2 相等温度到底算不算题目要求的是“更高的温度”所以相等温度不满足条件。这意味着正序写法里弹出条件是temperature[i] stack top等号不弹。倒序写法里弹出条件是temperature[i] stack top等号要弹。为什么倒序写法等号要弹因为倒序遍历时右侧可能存在与当前温度相等的位置但“第一个比当前温度更高”的位置在更远处。保留一个相等温度在栈顶会让stack[-1] - i给出一个错误答案比如等到的是相同温度而不是更高温度。所以倒序必须把等号弹掉保证栈顶永远是严格大于当前温度的位置。这个细节非常隐蔽我第一次写倒序版本时就栽在和的区别上。建议你自己跑一遍[73, 74, 75, 71, 69, 72, 76, 73]把倒序写法里的改成看看结果会差在哪里。5.3 栈被弹空时的处理正序写法里如果 while 循环把栈弹空了说明当前元素是“目前见过的最大的温度”它没有右侧更高温度候选正序视角下它还没遇到更大的直接入栈即可。倒序写法里如果栈弹空了说明右侧没有任何一个位置大于当前温度那么ans[i] 0。在代码里用if stack:来判断不要直接取stack[-1]——这一步很容易忘记一旦忘记就会IndexError。5.4 下标差的方向不要搞反ans[prev_index] i - prev_index和ans[i] stack[-1] - i这两个式子里都要求“大下标减去小下标”。如果你在正序写法里写成prev_index - i结果全是负数而且答案语义完全错乱。我的习惯是每写一行涉及下标差的地方都会在注释里标注“后出现的下标 - 先出现的下标”。写代码之前先想清楚这是“第几天之后”而不是“过了几天”。5.5 语言之间的差异如果你用 Python注意while stack and ...这个写法里stack作为布尔值是 False 当且仅当栈为空所以要先判断栈非空再取stack[-1]这个顺序不能反。如果你用 C/Java用while (!stack.isEmpty() ...)或者while (!st.empty() ...)同样要注意短路求值。不要小看这些小细节很多人在白板面试时就是因为stack[-1]取到了空栈或者和用错导致整个解法被面试官质疑。6. 一题吃透一类题单调栈模板的迁移路径6.1 找出“右边第一个更大/更小元素”单调栈最常见的应用场景就是“找右侧第一个更大元素”或“找右侧第一个更小元素”这几乎是一整套题型的公共骨架。LeetCode 496下一个更大元素 I其实是 739 的子集先算出每个元素右侧第一个更大值再按nums1的查询顺序取值。LeetCode 503下一个更大元素 II循环数组常用技巧是把数组长度翻倍或者用i % n来模拟循环。模板就是在 739 的基础上把遍历范围从n改成2n答案只更新前 n 个位置。LeetCode 84柱状图中最大的矩形要找的是“左右两侧第一个更小位置”用来确定当前高度能扩展的宽度边界。这是单调栈另一个方向的用途——从“找更大”变成“找更小”思路一模一样只是弹栈条件要反过来。LeetCode 42接雨水本质上是找每个凹槽两侧的边界用单调递减栈可以在入栈/出栈过程中计算横向的水量。所以你看739 虽然是“模板题”但它几乎是整个单调栈题型的枢纽。把它吃透后面那一堆题都能省不少力气。6.2 从模板题到实战题的迁移方法我的经验是遇到一道新题先问三个问题问题是要求“某个位置左/右侧第一个比它大/小的元素”吗是否可以通过维护一个栈内递减/递增序列让不必要的元素被提前淘汰答案的计算是否依赖于“下标差”或“左右边界的范围”如果这三条里有两条以上成立那基本就是单调栈能解决的问题。拿到题先别急着写把“栈内存的是什么、弹出条件是什么、弹出时更新什么”这三点写在纸上写清楚再动手准确率会高很多。6.3 实际刷题中的建议顺序如果你的目标是快速掌握单调栈这类题型我建议按这样的顺序刷LeetCode 739 每日温度入门理解正序递减栈LeetCode 496 下一个更大元素 I用哈希表记录结果LeetCode 503 下一个更大元素 II循环数组的处理LeetCode 84 柱状图中最大的矩形找左右更小边界LeetCode 42 接雨水综合应用理解水量与栈的关系这五道题做完之后你对单调栈的理解会比背十道题更扎实。每次做新题时都回头对比一下 739想想“这题和 739 的差别在哪里、为什么用同样的模板也能做”这个对比过程本身就是很好的学习方式。6.4 进阶为什么不只存下标还可以存额外状态有些单调栈问题里光存下标不够还要额外存一些状态。比如计算接雨水时弹出栈顶后需要知道“新的栈顶是谁”才能确定水的左边界。这时栈里存下标就够了因为通过temperatures[stack[-1]]能拿到具体值。但如果题目的状态更复杂你完全可以在栈里存一个元组(index, value)或者用结构体。739 的模板之所以经典就是因为它用最简单的“只存下标”展示了单调栈核心思想。我在实际工程里也经常会用到这种思路比如处理时间序列数据时要查找每个时间点之后第一个超过阈值的时间点这就是一个很典型的单调栈场景。算法题并不是只为了面试很多处理“窗口内候选淘汰”的问题底层思路都是一样的。说回这道题本身。我在带身边朋友刷题时最常说的一句话是不要背模板要背的是模板背后的淘汰逻辑。739 的递减栈本质上就是“把那些永远不可能成为答案的候选提前丢掉”。一旦你理解了这个淘汰逻辑无论题目换成找更大还是找更小是正序还是倒序是数组还是循环数组你都能很快写出正确的代码。建议你把上面两种写法的代码各手动模拟两遍再对比着去做 496、503、84 这几道题你会明显感觉到单调栈已经不再是需要死记硬背的难点而是一个顺手的工具。
