企业官网建设流程全解析

这题我刷了整整三遍才算真正吃透。第一次看见“每日温度”的时候，心想这不就是两层循环暴力扫一遍的事，结果一提交，超时得明明白白。后来才意识到，这道题根本不是考你循环嵌套写得多熟练，它真正想让你掌握的是单调栈这个数据结构。标题里写的“1.20单调栈（每日温度）”，也就是我刷题笔记里专门给单调栈开的一节，拿这道经典题来切入，再合适不过了。

先给没见过的朋友说下这道题在讲什么：给你一个每天温度的数组，比如[73, 74, 75, 71, 69, 72, 76, 73]，让你返回一个新数组，里面每个位置的值表示“要等多少天才会出现比这一天更高的温度”。等不到就填0。比如第0天是73度，第1天74度就比它高了，所以结果是1；但第4天是69度，要等到第5天72度才算更高，所以结果也是1。套用到每个位置，输出的就是[1, 1, 4, 2, 1, 1, 0, 0]。

这道题适合谁？适合刚开始刷算法题、卡在“暴力解通过不了”阶段的人，也适合那种知道单调栈这个名字、但一直没搞懂它到底怎么用的人。这篇文章我会从暴力解法讲起，把单调栈的原理掰开揉碎，给出可以直接复用的代码写法，顺便把调试过程中最容易踩的坑一起说了。

1. 题面与思路拆解：从“等几天”这个直觉问题开始

1.1 把题目翻译成大白话

“每日温度”其实是在问一个非常生活化的问题：今天这个温度，接下来还要熬几天才能遇到一个更暖和的日子？注意它的条件有两层，第一层是温度必须“更高”，不是持平也不是更低；第二层是去找“最近的”那个更高温度的日子，算它们之间隔了几天。

这两层条件合在一起，本质就是在做一件事：对数组中的每个位置，找到它右侧第一个比它大的元素，记录这个元素和它的距离。这个描述一出来，懂一点算法的朋友应该已经嗅到了熟悉的味道——这就是经典的“下一个更大元素”变种题（LeetCode 496就是那个题）。只不过496要求返回的是一段距离，每日温度要求返回“间隔天数”，代码上就差一个下标相减。

还有一个很容易看漏的细节：题目里说的是温度，但实际比较是把温度当作数字处理，与日期无关。也就是说，只要数组内部数值满足关系，日期只用来计算距离。数字本身没有单位，只是用来做大小比较的。

1.2 暴力解法为什么一定超时

我当初第一次写的暴力解法很简单，两层循环：

外层循环枚举每一个位置i，内层循环从i+1开始向右找第一个大于temperatures[i]的数，找到就break，记录距离，找不到就填0。

vector<int> dailyTemperatures(vector<int>& temperatures) { int n = temperatures.size(); vector<int> 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; }

这个写法的思路老实说没问题，逻辑也对，但一旦数据量上来就完蛋。假设数组长度是n，最坏情况下温度序列单调递减，也就是每天都比前一天冷，比如[100, 99, 98, ..., 1]。这种情况下，内层循环每次都把后面的元素全部扫完还找不到更大的，所以两两组合都要跑一遍，总操作次数接近n²/2，时间复杂度O(n²)。

当n是10万级别的时候，n²就是百亿量级，在标准OJ上跑1秒基本是做梦。就算你的本机CPU很强，也会明显等上好几秒。所以这道题的存在意义，某种意义上就是逼你放弃暴力枚举。

1.3 题目隐含的三种情况总结

在所有测试数据里，每个位置只可能出现三种结果：

• 右侧存在更高温度，返回最近更高温度与当前日期的差值。
• 右侧不存在更高温度，返回0。
• 温度相等的情况不算“更高”，必须严格大于。

这三种情况看起来简单，但在写单调栈的时候，分支判断稍一马虎就会错。很多人是在“相等”这个边界上栽的跟头，后文我会专门说到这个细节。

2. 单调栈的直觉来源：为什么栈这个结构天生合适

2.1 一个“回调任务”的视角

我第一次想明白单调栈能用在什么场景，是通过一个厨师做菜的类比。假设你手头有一堆外卖订单，每单上都写着出餐时间，你先接到的订单放在桌上的文件筐里，后到的订单往上一放。如果某一刻突然来了一个“紧急加急单”，你会从最上面开始往下翻，找到第一个时间比它晚的订单。

栈就是这样一个文件筐：你只从最上面拿东西。而“每日温度”这个问题，恰恰可以理解成“每来一个更大的温度，就要把前面所有比它小的温度结算掉”。这副“后进先出”的结算顺序，和栈在结构上完全一致。

2.2 单调性：栈内元素的排列规律

单调栈就是在普通栈的基础上，维持一种“从栈底到栈顶单调递增或递减”的特征。放在“每日温度”里，我们维持的是一个从栈底到栈顶递减的栈。递减意味着栈顶元素是当前栈里最小的那个（注意这里说的是栈内保留的“温度值”或“温度对应的下标”，后文我统一探讨）。

为什么非要把栈维持成递减的？因为当我们从左到右遍历数组时，一旦遇到了一个比栈顶元素温度更高的日子，栈顶元素作为“等待更高温度的人”，就可以立马结算出它的答案。而这个结算顺序天然是离当天最近的一个未结算元素，恰恰是由栈顶元素提供的。如果栈不是递减的，栈顶元素就不一定是“最近等待结算”的人，逻辑就乱了。

2.3 栈里存下标，还是存温度？

新手最容易纠结的一个点是：栈里到底放数组的值，还是放数组的下标？

在“每日温度”这道题里，答案很明确：必须存下标。原因很简单，我们最终要计算的是间隔天数，也就是两个日期下标之差。如果不存下标，光有温度值，算不出距离。而且当温度值相同的时候，光看数值也无法区分是哪个位置。所以，即使你在弹出栈顶元素时能用temperature[st.top()]取到温度，也要把下标本身入栈。

这里有一个可以举一反三的经验：凡是需要“求距离”“求区间长度”“求下标差”的问题，栈里存下标基本是通用做法；如果题目只要求比较大小、不涉及位置，那也可以直接存值，但那样的题目很少出现在“单调栈”系列的主要练习题里。

3. 两种正确写法实操：正向遍历与反向遍历

3.1 正向遍历的解法（推荐重点掌握）

正向遍历的思路，是让栈里保留“还没有找到更高温度的日子的下标”。每来一个新日子，就用它的温度去和栈顶日子的温度比较，如果栈顶日子的温度低于新日子，说明栈顶日子的“更高温度”出现了，立刻出栈并计算距离。

vector<int> dailyTemperatures(vector<int>& temperatures) { int n = temperatures.size(); vector<int> ans(n, 0); stack<int> st; // 栈里存下标，温度从栈底到栈顶递减 for (int i = 0; i < n; ++i) { while (!st.empty() && temperatures[i] > temperatures[st.top()]) { int idx = st.top(); st.pop(); ans[idx] = i - idx; } st.push(i); } return ans; }

这个代码的过程，我来手推一遍，这样你才能真正理解栈里发生了什么。

以[73, 74, 75, 71, 69, 72, 76, 73]为例：

• i=0，温度73，栈空，直接把0压栈。栈内状态：[0(73)]
• i=1，温度74，stack顶是0，温度73<74，所以0出栈，ans[0]=1-0=1。然后栈空，把1压栈。栈内：[1(74)]
• i=2，温度75，栈顶是1，74<75，1出栈，ans[1]=2-1=1。栈空，把2压栈。栈内：[2(75)]
• i=3，温度71，栈顶是2，75>71，没有形成“大于”，所以2不动，把3压栈。栈内：[2(75), 3(71)]
• i=4，温度69，栈顶是3，71>69，不满足出栈条件，把4压栈。栈内：[2(75), 3(71), 4(69)]
• i=5，温度72，此时栈顶是4，69<72，4出栈，ans[4]=5-4=1。接着栈顶是3，71<72，3出栈，ans[3]=5-3=2。再接着栈顶是2，75>72，停止。把5压栈。栈内：[2(75), 5(72)]
• i=6，温度76，栈顶是5，72<76，5出栈，ans[5]=6-5=1。栈顶是2，75<76，2出栈，ans[2]=6-2=4。栈空，把6压栈。栈内：[6(76)]
• i=7，温度73，栈顶是6，76>73，不满足出栈条件，把7压栈。栈内：[6(76), 7(73)]

遍历结束，栈里还剩下6和7没有出栈，说明它们右侧没有更高温度了，ans[6]和ans[7]保持初始值0。最终答案是[1, 1, 4, 2, 1, 1, 0, 0]。

这个手推过程中，你有没有发现一个关键现象：每个元素最多入栈一次、出栈一次，所以总操作是2n级别，时间复杂度严格O(n)。单调栈“用空间换时间”的优势，就在这里体现出来了。

3.2 Python版本对照

如果平时你用Python刷题，下面这份写法更简洁，逻辑完全一致：

def dailyTemperatures(temperatures): 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 ans

Python这边有一个小细节：list的append和pop就是栈的push和pop操作，时间复杂度都是O(1)，不需要额外引入模块。用stack[-1]来取栈顶元素，比用stack[len(stack)-1]更简练。

3.3 反向遍历解法：换个方向其实更舒服

正向遍历是“来一个新元素，找它之前等待结算的人”。反向遍历的思路则是：从右往左走，维护一个从栈底到栈顶递增的栈，栈里存的是“右侧已经见过的、温度更高的日子的下标”。每到一个位置，不断弹出栈顶比当前温度低的下标，最终剩下的栈顶（如果存在）就是“右侧第一个更高温度”的日子。

vector<int> dailyTemperatures(vector<int>& temperatures) { int n = temperatures.size(); vector<int> ans(n, 0); stack<int> st; for (int i = n - 1; i >= 0; --i) { while (!st.empty() && temperatures[i] >= temperatures[st.top()]) { st.pop(); } if (!st.empty()) { ans[i] = st.top() - i; } st.push(i); } return ans; }

注意这里出栈的条件是temperatures[i] >= temperatures[st.top()]，意思是“把右边不比当前温度高的全部丢掉”，因为有了当前这个更高的温度，右边那些更低的温度对于更左边的日子来说已经没有参考价值了。而且特别注意，这里是大于等于，等于也被弹出去，因为等于也不能算“更高”。

反向遍历的好处是什么？代码更贴合“第一个更大元素”的语义，因为栈顶天然只剩下右侧更高的下标。但它也有一个隐蔽风险：很多人在写反向遍历的时候，容易把出栈条件写成大于号，导致碰到相等温度时栈没清干净，答案不正确。所以两种遍历方式，我建议你至少把正向写法吃透，反向写法作为检验思维是否真正掌握的练习。

3.4 边界情况逐一过一遍

写算法题，边界情况永远是最容易出错的环节。“每日温度”常见的边界情况包括：

• 数组长度为1，比如[30]。此时没有“右侧”，直接返回[0]。
• 全部元素都相等，比如[50,50,50]。由于要满足严格大于，没有任何一个位置能等到更高温度，结果全是[0,0,0]。
• 全部单调递增，比如[30,40,50,60]。每个位置都等一天就遇到更高温度，结果全是[1,1,1,0]。
• 全部单调递减，比如[60,50,40,30]。没有任何位置能等到更高温度，但每个元素都在栈里走了一遭，最后全留在栈里没被弹出。

编写完代码，我建议你在脑子里对这几个极端场景各走一遍，比盲写一百行测试数据都有用。

4. 单调栈模板提炼与题型延伸

4.1 从每日温度里抽出一个万能模板

练完这道题，我的经验是：你不该只记住这道题的代码，而应该把单调栈的处理框架抽出来，当作固定套路来记忆。我在自己笔记里是这么写的：

• 遍历数组
• 栈里维护“尚未找到答案”的候选下标
• 每来一个新元素，把栈内所有“被新元素解开答案”的元素弹出并结算
• 弹完之后，新元素下标入栈，等待未来处理
• 循环结束后，栈内剩余元素一律没有更优答案

有了这个框架，遇到任何“下一个更大/更小元素”“左右第一个比它大/小的位置”类题目，都可以直接套用它，再根据题目语义决定栈的单调方向、比较符号、结算方式。

4.2 几道经典变体如何复用这个模板

第一道变体是“下一个更大元素”系列。它给你两个数组，本质上是同一套单调栈逻辑，只是多了一个哈希表映射的过程。你先对第二个数组做一次正向单调栈，求出每个元素右边第一个更大的值，再把结果存到哈希表里，最后遍历第一个数组取值即可。

第二道变体是“柱状图中最大的矩形”。这道题表面上和温度毫无关系，但思路恰恰也是单调栈，只是维护的方向相反，要找左右两侧第一个更矮的柱子，栈内从底到顶保持递增。结算面积时，高度由弹出元素给定，宽度由左右边界决定。如果你把“每日温度”彻底吃透了，再看这道题，会发现很多思路都是相通的。

第三道变体是“接雨水”。接雨水要找到每个位置左右两侧的最高边界，经典解法是用双指针，但也可以用单调栈来算。栈底到栈顶递减，遇到比栈顶高的，弹出栈顶并按宽度和高度差来累加水量。逻辑略绕，但核心骨架仍然不变。

我提这些变体，不是让你现在就去把它们全刷完，而是告诉你：花在“每日温度”上的时间，不需要多，但一定要把它背后的模板想透。它会成为你做单调栈类题目的思考起点。

4.3 变形时最容易跑偏的三个关键差异

变体题目虽然都是单调栈，但有三处容易跑偏的地方。

第一个是“大于”和“大于等于”的区别。“每日温度”要求严格更高，所以正向遍历用大于号弹出；如果题目允许相等也算，那就要把符号改成大于等于，漏掉等于号会导致答案错误。

第二个是“找更大”还是“找更小”的方向。这个决定栈内的单调方向。找“下一个更大”基本是栈内递减；找“下一个更小”基本是栈内递增。搞反这个，栈顶的比较逻辑全乱。

第三个是结算内容的差异。“每日温度”结算的是距离，所以出栈后算两个下标之差；“下一个更大元素”结算的是值本身；“柱状图最大矩形”结算的是面积。这说明单调栈是骨架，结算公式是灵魂，两者需要一起搭配使用。

4.4 复杂度分析的严谨推导

很多人背过“单调栈时间复杂度O(n)”，但不知道它为什么是O(n)。这个一定要能自己推出来。

每个下标只会被push入栈一次。它一旦被pop出来，就说明已经找到了答案，之后不会再入栈。所以对于长度为n的数组，push操作总数等于n，pop操作总数也小于等于n。while循环整体执行的次数不超过入栈总次数，也就是O(n)级别。再加上外层循环n次，总复杂度仍然O(n)。空间复杂度方面，栈最多存n个元素，所以是O(n)。

这套推导逻辑，在面试手写复杂度分析的时候直接说“每个元素入栈出栈最多一次，所以均摊O(n)”就够了。说“均摊”是因为while循环看起来可能执行很多次，但整体加总不超过n，这种说法体现了复杂度分析的专业程度。

5. 常见问题与排查技巧实录

5.1 我实际调试中遇到的三个典型错误

第一个错误是：把下标和温度混着用。我在写代码时有一次不小心在比较温度的地方写成了i > st.top()，一眼看过去好像很合理，但它其实是在比较下标，比较的完全不是温度。这个问题在数据量小、巧合匹配的情况下很难发现，直到我拿一组顺序比较特殊的数据测试，才暴露出问题。解决方法是严格明确：凡是取温度值，必须写temperatures[st.top()]，凡是取下标，直接操作st.top()或i，不要混。

第二个错误是：忘了处理栈里剩余元素。我早期写正向解法，从数组开头遍历完就以为大功告成，根本没考虑栈里还剩没弹出的元素。结果栈底那些“永远等不到更高温度”的下标，ans位置一直保持0，表面上看好像也没错。但有一次我把初始ans直接初始化为-1，输出就乱了。严格来说，栈里剩余元素其实不需要特殊处理，因为它们的答案就是默认值0。

第三个错误是：把比较符号写成>=。在正向遍历里，如果用>=弹出，两个温度相等也会触发结算。但题意要求严格更高，等于不能算。一旦出现连续相同温度，结果就会全错。这个坑我栽过两次，现在每次写完单调栈都会专门检查比较符号。

5.2 用特殊输入序列做自测

我给自己定了一套自测输入，每次写完单调栈必跑：

• [1, 2, 3, 4, 5]，递增序列，结果必须是[1,1,1,1,0]
• [5, 4, 3, 2, 1]，递减序列，结果必须是[0,0,0,0,0]
• [1, 1, 1, 1]，全相等序列，结果必须是[0,0,0,0]
• [30]，单元素，结果必须是[0]
• [73, 74, 75, 71, 69, 72, 76, 73]，标准测试，必须是[1,1,4,2,1,1,0,0]

只要这些输入全部通过，基本可以确认代码没有大问题。尤其是全相等和单元素这两个容易踩坑的输入，很多人都会忽略。

5.3 排查逻辑时的三个步骤

如果你发现自己写的单调栈代码在某组数据上错了，我建议按顺序排查：

第一步，用笔手动推演一遍小规模输入。推演的时候把栈的状态一行一行列出来，就像我在前面用的手推方式。只要推演过程中发现某一步的栈状态和你预期不一致，问题定位就完成了。

第二步，给代码加临时调试输出。在for循环里打印i、当前温度、栈内所有元素、弹出下标、结算值。这样能看到真实运行和手推的差异在哪。

第三步，把题目条件重新逐字读一遍。很多问题不是出在算法上，而是出在对题意的理解有偏差。比如“每天的温度”其实是“非负整数”，但温度数值本身不重要，重要的是大小的相对关系。

6. 个人实操心得与学习建议

自己刷完这道题之后，我最大的感受是：单调栈的核心不在“栈”这个数据结构本身，而在于“延迟结算”这四个字。温度低的那些日子，明明当时没有答案，但你不急着给它填结果，而是把它放进栈里存着，等到答案出现的那一天再一次性算清楚。这和大脑处理复杂问题的思路很像——不必要的事先不处理，等条件成熟了再集中处理。

练习单调栈，我有三个经验可以分享。

第一个经验是，先别急着看题解，先自己尝试用暴力法写一遍。暴力法虽然超时，但它会逼你认真分析“每个位置到底在找什么”。一旦你发现暴力法里大量重复扫描了已经访问过的元素，你就离单调栈的想法不远了。这一步是建立直觉的关键。

第二个经验是，手推栈状态一定要推到三次以上。“每日温度”的代码即便背下来，如果不理解栈里那个“从底到顶递减”的性质是怎么维持的，题目换个马甲你就认不出来了。我逼自己把标准测试数据从头到尾推了五遍，直到闭着眼能说出来每一步的栈内容，才开始做后面的变体题。

第三个经验是，做变体题时，时刻提醒自己“模板相同，结算不同”。看到新题先确认三个问题：找更大还是更小？栈内递增还是递减？结算的是距离、值还是面积？这三个问题确认完，代码框架立即可套。

如果你现在刚开始接触单调栈，不要指望一次就能完全消化。今天先把正解法会写、会推导，明天再试反向解法，等你能独立把“柱状图中最大的矩形”做出来的时候，单调栈才真正成为你自己的工具。

这道题我从超时写超时，到完全吃透，大概花了两三天。中间一度很想放弃，但后来发现，单调栈这种“延迟结算”的思路，其实每天都在生活里发生。比如你买了一堆东西放在购物车里，等到打折的时候再一起结算，这就是“延迟结算”。理解了这一层，代码里的栈也就没那么吓人了。希望这篇文章，能帮你把这道题从“背过”变成“想通”。