周末刷题刷到 LeetCode 739“每日温度”第一反应是“这不就是找下一个更大元素的距离吗”但真正手写的时候我在单调栈的边界条件上卡了快一个小时。这道题太经典了几乎每个讲栈的专题都会把它放在第一个可它越基础越值得掰开揉碎讲清楚。这篇文章我会从暴力解法开始一步步推导到单调栈把代码里每一个细节为什么这么写讲明白也把我实际调试过程中踩过的坑全部整理出来。适合刚接触单调栈的读者也适合刷了题但总记不住套路的同学。1. 先把题目读透数组里找“下一个更高温度”的距离1.1 题目到底在算什么东西给定一个整数数组temperatures里面记录的是每天的天气温度要求返回一个新数组answeranswer[i]表示“从第 i 天开始要等多少天才会出现一个比第 i 天更高的温度”。如果后面永远没有更高的温度就用 0 填充。比如题目给的示例temperatures [73, 74, 75, 71, 69, 72, 76, 73] 输出 [1, 1, 4, 2, 1, 1, 0, 0]逐个看第 0 天 73 度第 1 天就是 74 度所以等 1 天第 1 天 74 度第 2 天 75 度所以等 1 天第 2 天 75 度要等 4 天到第 6 天的 76 度才更高第 6 天 76 度之后没有比它更高的所以是 0第 7 天是最后一天没有任何后续也是 0。注意一个关键点它要的不是“更高的温度是多少”而是“距离是多少天”。所以最终结果是一个下标差值不是温度差。这个点看起来简单但很多人写代码时会习惯性地把温度值存进结果里方向就错了。1.2 暴力解法思路直接但代价不小最自然的想法是两层循环。外层固定第 i 天内层从 i1 开始往后找遇到第一个大于temperatures[i]的就记下距离j - i然后 break。如果内层循环跑完都没找到就记 0。class Solution { public: vectorint dailyTemperatures(vectorint temperatures) { int n temperatures.size(); vectorint ans(n, 0); for (int i 0; i n; i) { for (int j i 1; j n; j) { if (temperatures[j] temperatures[i]) { ans[i] j - i; break; } } } return ans; } };暴力解法的问题很明显最坏情况下数组是严格递减的比如[50, 49, 48, 47, ...]每个元素的内层循环都要扫描到数组结尾才发现找不到更高温度总复杂度是 O(n²)。当 n 是 10^5 级别时这个复杂度在 LeetCode 的测试用例上一定会超时。但暴力解法并不是完全没用。它的价值在于帮我们确认需求我们想知道的是“右边第一个比当前元素大的位置”。这个描述一旦写出来其实就已经接近核心解法了。1.3 手算一遍示例找找感觉光看示例可能不够我建议你动手在纸上画一画。把温度数组写成一列然后对每个位置向右画箭头指向第一个比它大的数字。73 指向 74距离 174 指向 75距离 175 指向 76距离 471 指向 72距离 269 指向 72距离 172 指向 76距离 176 没有记 073 没有记 0。画完之后你会注意到一个规律每一个箭头都指向“右边第一个更高的位置”。而暴力解法就是沿着每个起点向右一格一格试探。单调栈就是用一个栈来模拟这个过程避免重复扫描已经看过的位置。2. 从暴力到 O(n)单调栈是怎么想出来的2.1 问题本质下一个更大元素Next Greater Element“每日温度”本质上就是经典的“下一个更大元素”问题只不过题目要求返回下标距离而不是元素值本身。这类问题有一个非常标准的解法单调栈。为什么栈能解决这个问题想象你是一个裁判从左向右看每一天的温度。栈里保存的是“正在等待一个更高温度出现”的那些天的下标。新来的温度出现时它先去跟栈里的元素比较。如果它比栈顶对应的温度高那栈顶这天就可以“毕业”了它等到了第一个更高温度就是新来的这天。然后继续比较新的栈顶直到当前温度不再高于栈顶再把当前下标压入栈等待未来某个更高温度。这个过程听起来顺理成章但真要自己想到这个思路需要一点“后视”的视角当前温度不仅能决定自己的结果还能决定栈里那些“等待者”的结果。这正是单调栈的核心思想——用单调性维护一堆“有待解决”的元素当新元素出现时批量解决掉那些可以被解决的。2.2 栈的直觉等待区 毕业机制用一个生活类比来理解。假设你是班长给一排同学登记“谁比我高”。你从队头开始登记手上拿着一个本子记下身高暂时没找到更高同学的编号。当你走到一个新同学面前如果这个新同学比本子上最后一个同学高那最后一个同学就可以在他的记录里写上你的后面出现了更高的人距离就是当前编号减去你的编号。写完这个记录就把这个同学从本子上划掉。继续往前翻本子把所有比新同学矮的都划掉。直到本子上的下一个同学不再比新同学矮才把新同学的编号写到本子末尾。这里本子从底到顶身高是严格递减的。最矮的永远在栈顶。新同学到来时把栈顶一批比自己矮的全都清掉。这个结构就叫单调递减栈。为什么维护的是递减而不是递增因为我们要找的是“右边第一个更大”。栈里保存的是一批结果还没确定的天数它们的温度从左到右应该是递减的。如果从左到右出现了递增那前面那个较小的早就被后面那个较大的“解决”了不会留在栈里。换句话说栈里的元素互相之间是“还没找到更大值”的关系它们必须保持递减一旦递增出现说明前一个的答案已经在当前元素这里确定了。2.3 单调栈的标准形态先想清楚栈里存什么单调栈有两种维护方向一种叫单调递增栈一种叫单调递减栈名字都是从栈底到栈顶的顺序定义的。在“每日温度”这道题里我们需要的是从栈底到栈顶递减的栈。栈里存的是下标不是温度。原因很简单第 i 天的结果需要的是一个距离差值只有存下标才能在弹栈的时候用i - stk.top()算出距离。如果只存温度你还要额外开一个数组去映射下标完全没有必要。这个设计是整个题解的基础理解了它后面写代码时就不会在“栈里到底放什么”这个选择上纠结。3. 核心实现手把手把单调栈代码写出来3.1 完整代码一次遍历搞定所有结果直接上 C 实现这个版本也是我最后采用的写法class Solution { public: vectorint dailyTemperatures(vectorint temperatures) { int n temperatures.size(); vectorint ans(n, 0); stackint stk; for (int i 0; i n; i) { while (!stk.empty() temperatures[i] temperatures[stk.top()]) { int prevIndex stk.top(); stk.pop(); ans[prevIndex] i - prevIndex; } stk.push(i); } return ans; } };代码总共只有十几行但每一行都有讲究。我拆开讲一遍vectorint ans(n, 0)结果数组先全部初始化为 0。因为那些在数组结束后仍留在栈里的下标确实等不到更高温度0 就是正确答案。stackint stk栈里存下标。循环里while而不是if只要当前温度比栈顶大就不停地弹出。因为当前温度可能同时解决栈里多个“等待者”。temperatures[i] temperatures[stk.top()]严格大于才弹出。等值的情况不弹出后面会专门讲原因。最后stk.push(i)无论 asa 当前下标是否触发过弹出都要把自己放进栈里因为它自己也在等待“右边第一个比自己大”的元素。3.2 用示例跑一遍亲眼看看栈的变化我还是用[73, 74, 75, 71, 69, 72, 76, 73]把每一步栈的状态列出来。栈里存下标下面同时标出它们对应的温度。初始状态ans [0, 0, 0, 0, 0, 0, 0, 0]栈空。i0温度 73。栈空直接入栈。栈[0(73)]i1温度 74。74 73弹出下标 0ans[0] 1 - 0 1。入栈下标 1。栈[1(74)]i2温度 75。75 74弹出下标 1ans[1] 2 - 1 1。入栈下标 2。栈[2(75)]i3温度 71。71 75不入栈就错了不是直接把下标 3 压入。栈[2(75), 3(71)]i4温度 69。69 71压入下标 4。栈[2(75), 3(71), 4(69)]i5温度 72。72 69弹出下标 4ans[4] 5 - 4 1。再比较72 71弹出下标 3ans[3] 5 - 3 2。再比较72 75停止。入栈下标 5。栈[2(75), 5(72)]i6温度 76。76 72弹出下标 5ans[5] 6 - 5 1。再比较76 75弹出下标 2ans[2] 6 - 2 4。栈空入栈下标 6。栈[6(76)]i7温度 73。73 76压入下标 7。栈[6(76), 7(73)]循环结束后栈里剩[6(76), 7(73)]ans 的 6 和 7 保持默认的 0。最终结果[1, 1, 4, 2, 1, 1, 0, 0]和题目一致。注意 i6 那一步温度 76 同时解决了栈里两个等待者。这就是单调栈的威力一次高效的比较批量更新多个答案。3.3 复杂度分析为什么是 O(n) 而不是看着像 O(n²)有人可能会疑惑while 循环里每次都可能弹出很多元素最坏情况是不是 O(n²)不会。关键在于每个下标最多只会被压入栈一次也最多只会被弹出一次。弹出后它再也不会回到栈里。所以所有 while 循环中总的弹出次数之和不超过 n。加上外层循环的 n 次入栈操作总操作次数是 2n 级别时间复杂度 O(n)。空间复杂度方面栈在最坏情况下要存储全部 n 个元素比如数组严格递减[50, 49, 48, ...]每个元素都是直接入栈、从不弹栈所以空间是 O(n)。这里有一个非常直观的复杂度理解方式每一次“处理”要么是入栈n 次要么是出栈最多 n 次没有第三种操作。所以整体是线性的。3.4 边界情况空数组、全递增、全递减写这个代码还有几个边界场景值得单独验证。空数组n0ans为空直接返回正确。全递增数组[1, 2, 3, 4, 5]每个元素都会在新元素到来时被弹出结果应该是[1, 1, 1, 1, 0]。代码执行时i4 元素 5 入栈后循环结束最后一位是 0其余都在弹出时算到了距离。正确。全递减数组[5, 4, 3, 2, 1]任何一个温度后面都没有更高的所有下标都会留在栈里结果全 0。正确。相同温度[1, 1, 1, 1]相等不弹出所有下标全部留在栈里结果全 0。因为“更高温度”要求严格变大等值的日子不算是更高所以 0 是正确的。这些边界看起来简单但恰恰是很多人在面试时翻车的地方。尤其“相等不弹出”这个细节如果你在处理“下一个更大元素”时用成就会把等值元素错误地当作答案。4. 换个方向也能做从右往左的解法与细节对比4.1 从右往左遍历的思路很多人第一次接触单调栈学的都是从左向右的版本。但其实这道题还有一个从右向左的写法理解之后对单调栈的理解会更完整。思路是从数组末尾开始向前遍历。栈里依然存下标但栈底到栈顶递增还是递减答案是栈底到栈顶也是递减的不过意义不同。从右往左时我们已经知道了“右边”的情况所以栈里保存的是当前位置右侧的温度序列。如果待入栈的下标对应温度比栈顶小或相等说明栈顶的“潜力”比当前元素弱可以弹出。最后栈顶如果是空的说明右侧没有更大值答案为 0否则答案是栈顶下标 - 当前下标。代码是这样的class Solution { public: vectorint dailyTemperatures(vectorint temperatures) { int n temperatures.size(); vectorint ans(n, 0); stackint stk; for (int i n - 1; i 0; --i) { while (!stk.empty() temperatures[i] temperatures[stk.top()]) { stk.pop(); } ans[i] stk.empty() ? 0 : stk.top() - i; stk.push(i); } return ans; } };注意这里 while 的条件用了和从左往右版本的不同。为什么因为从右往左时栈顶代表的是当前元素右边的候选者。如果栈顶温度小于等于当前温度那这个栈顶元素对当前元素和更左边的元素来说永远不可能是“更高温度”的候选者因为有当前温度挡在它左边且当前温度同样更高或相等。所以必须弹出。4.2 两个版本对比谁更好记我把两个版本放在一起对比方便你理解它们本质是同一套逻辑维度从左往右从右往左遍历方向0 到 n-1n-1 到 0弹栈条件当前温度大于栈顶温度当前温度大于等于栈顶温度答案更新时机弹栈时更新被弹出下标的结果入栈前直接计算当前下标的答案栈内剩余含义未遇到更大温度的下标当前元素右侧可能的更大温度候选项记忆难度相对直观稍绕但代码更紧凑我个人更推荐新手先掌握从左往右的版本因为它的“等待者毕业”叙事最贴合直觉。从右往左的版本更适合作为进阶理解用来帮你反向验证单调栈的原理。4.3 等号到底怎么处理一个很容易搞混的细节两个版本的弹栈条件一个用一个用这可能是整个题解里最容易混的点。我专门讲一下。从左往右时我们关心的是“严格大于”当前温度的日子等值不算是更高温度。所以当前温度temperature[i]遇到栈顶temperature[stk.top()]只有才需要弹出。如果等值也弹出就会错误地把等值那天当作更高温度算出错误的距离。从右往左时等值必须弹出因为栈里维护的是“当前元素右侧严格更高的候选者”。如果保留一个等值的栈顶那它永远无法成为“更高温度”并且它会挡住后续所有比它矮的、可能是正确答案的候选者。这个细节如果不注意从右往左版本会输出错误结果。实在记不住两个版本的等号规则时我建议训练时在两个版本上都跑一遍[1, 1, 1, 1]这个用例从左往右结果应该全 0从右往左结果也应该全 0。如果你的代码在某个版本上输出了非 0就说明等号处理反了。5. 实战经验常见报错与排查方法5.1 输出结果全为 0 的排查思路我在调试时遇到的第一个问题就是输出全 0。检查代码发现我把temperatures[i] temperatures[stk.top()]写反了变成了temperatures[i] temperatures[stk.top()]。这样栈顶永远比当前温度大while 条件永远不成立每个下标都是直接入栈自然不会有任何弹栈动作答案全是 0。排查方法很简单在 while 循环里加一行printf或者cout输出每次弹出和入栈的下标。如果循环一圈下来一条弹出日志都没有那十有八九是条件反了或者数组根本没进循环。5.2 结果值偏大多半是下标计算错了还有一次输出结果明显偏大比如示例中第 2 天应该输出 4我写成了 5。后来发现我把弹出的下标变量名写混了用了i - stk.top()而不是i - prevIndex。由于先调用了stk.pop()再访问stk.top()得到的是下一个栈顶元素距离自然算错了。正确做法是先把栈顶下标取出来保存到变量里再 pop再用当前下标减去保存下来的prevIndex。顺序错了结果就是典型的“偏大且看似随机”。5.3 把 while 写成 if 的后果有一个很容易忽略的点while 和 if 在这个题里不能互换。我见过不少人在初学时把代码写成if (!stk.empty() temperatures[i] temperatures[stk.top()]) { int prevIndex stk.top(); stk.pop(); ans[prevIndex] i - prevIndex; } stk.push(i);这样写的问题在于当前温度一次只能解决一个“等待者”。如果栈里有很多比当前温度低的元素它们全都应该被当前温度“解决”但因为只判断了一次后面的等待者会一直留在栈里等到后面某个温度再处理结果就会偏大。要理解为什么栈里可能积压多个“等待者”想想温度序列[70, 71, 72, 75]。处理到 75 时栈里依次会有 72、71、70 等待被 75 解决。如果是 if栈里只会弹出 7271 和 70 就要等后面的温度显然错误。用 while 就能一次性全部弹出。5.4 单调栈系列的延伸刷完这题还能刷什么739 是单调栈里最简单的一道。刷完之后可以继续练习这几个变体它们都是在“维护一个单调栈”的框架下做文章LeetCode 496 下一个更大元素 I给两个数组求 nums1 中每个元素在 nums2 中的下一个更大元素值。核心是先用单调栈预处理 nums2再用哈希表映射。LeetCode 503 下一个更大元素 II把数组变成循环数组处理方式是遍历两遍数组用下标取模或者把数组拼接两遍。LeetCode 84 柱状图中的最大矩形单调栈的应用升级版维护高度的同时还要计算宽度栈底到栈顶递增。LeetCode 42 接雨水可以用单调栈维护递减高度也可以在左右方向用双指针思路相通。LeetCode 901 股票价格跨度把“下一个更大元素”反过来求当前元素向左看连续小于等于它的天数。这五个题刷完单调栈基本就入门到中等难度了。建议每个题都用从左往右版本写一遍再尝试从右往左版本做到两种视角都能流畅写出代码。6. 一道题背后的复盘我的最终模板与刷题心得做完整道题之后我很想把一个实用模板沉淀下来方便以后遇到同类题直接套用。我自己的习惯是把这个模板固定成四步第一步确定栈的单调方向。要求“右边第一个更大的距离”就维护从栈底到栈顶递减的栈要求“右边第一个更小的距离”就维护递增栈。第二步确定弹栈条件。从左往右时让当前元素和栈顶比较如果当前元素大于栈顶且我们找的是“更大值”就弹出如果找“更小值”就反过来。第三步确定答案更新的位置。弹栈的时候被弹出的那个下标的结果在当前下标这里确定所以是ans[stk.top()] i - stk.top()如果是入栈前先算当前下标的结果那就换成从右往左的版本。第四步检查等号。找“严格大于/小于”时确定一下左右遍历方向对应的条件尤其注意从右往左时通常要处理等值出栈。我还发现一个复习技巧每做完一道单调栈题用 2-3 组特殊用例去验证比如全递增、全递减、全部相等、空数组。跑这些用例出错的位置往往就是你还没理解的细节。我在 739 这道题上跑了不下五组用例才把等号问题彻底搞透。回到最开始的问题为什么一个看起来简单的“找更高温度距离”要引入栈因为暴力解法做了大量无效的重复扫描。栈把已经扫描过但还没确定结果的元素放在一个有序结构里新元素到来时用一个 O(1) 的栈顶比较快速决定这些旧元素是“毕业”还是“继续等待”。这才是整个方案的灵魂。最后再分享一个实战小技巧面试写这道题时不要急着写代码。先把暴力解法讲清楚再引出单调栈优化的动机然后口头推演一遍示例。面试官更看重你能否清晰表达“为什么用栈”以及“时间复杂度的严谨推导”。代码写对只是及格讲清楚思路才是加分项。我自己现在刷单调栈专题每道题都会刻意先讲思路再动手这个习惯帮我在面试中省了不少麻烦。