企业官网建设流程全解析

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，从 i+1 开始往后扫，找到第一个大于 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] 走一遍从左往右的单调栈：

• i=0，温度 73，栈空，入栈，栈：[0]
• i=1，温度 74，大于栈顶 0 号位的 73，弹出 0，ans[0]=1-0=1，入栈 1，栈：[1]
• i=2，温度 75，大于栈顶 1 号位的 74，弹出 1，ans[1]=2-1=1，入栈 2，栈：[2]
• i=3，温度 71，小于 75，入栈 3，栈：[2, 3]
• i=4，温度 69，小于 71，入栈 4，栈：[2, 3, 4]
• i=5，温度 72，大于栈顶 4 号位的 69，弹出 4，ans[4]=5-4=1；继续比较，72 大于栈顶 3 号位的 71，弹出 3，ans[3]=5-3=2；72 小于栈顶 2 号位的 75，停止，入栈 5，栈：[2, 5]
• i=6，温度 76，大于栈顶 5 号位的 72，弹出 5，ans[5]=6-5=1；76 大于栈顶 2 号位的 75，弹出 2，ans[2]=6-2=4；栈空，入栈 6，栈：[6]
• i=7，温度 73，小于 76，入栈 7，栈：[6, 7]

最终答案 [1, 1, 4, 2, 1, 1, 0, 0]，和题目输出一致。细看这个推演过程，你会发现每个元素确实只入栈出栈一次：比如 75 在第 6 天才弹出，是因为它一直等到 76 才看到第一个更高的温度，中间那些 71、69、72 都比它小，压根没资格触发它的结算。

3.2 边界用例自测清单

写完之后别急着交，我习惯用下面这组用例快速自测，几乎能覆盖所有坑：

特别是最后两组，专门用来检查你没把“大于等于”和“大于”搞混。从左往右写法里，弹出条件是 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，去看 t+1 到 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 我见过的常见错误速查表

最后把实际写题时会犯的错误集中列一下：

前三个错误我都在不同时期犯过，尤其是“存值不存下标”，一错就是结构性错误，改起来比存下标麻烦得多。建议新手第一次写的时候，先在注释里标明栈的类型是 List[int]，里面是下标，不是温度，能有效减少潜意识把值塞进去的冲动。

4. 同类题串讲：739 刷完之后，这些题可以接着上

4.1 单调栈题型的两种骨架

739 刷熟之后，你会发现单调栈在 LeetCode 里基本分成两路。第一路是“下一个更大/更小元素”系列，核心模式和 739 几乎一样：维护一个栈，新元素触发弹出时结算答案；区别只是方向、严格性、答案存的是距离还是元素值。第二路是“柱状图/接雨水”这类贡献面积题，栈里弹出一个元素时，除了要知道它等到了谁，还要算左右边界夹出来的宽度或面积，单调栈里“弹出即结算”的思想直接复用。

搞清楚自己刷的题属于哪一路，比盲目背代码重要。739 是第一路的经典代表，所以你会看到很多博客把它和 496、503、901 放在一起讲；等你要挑战 84、42 时，又会有专门讲第二路的文章提到 739，说它是那道题的“前置铺垫”。这也是我推荐它作为入门题的原因——它是连接这两个分支的枢纽。

4.2 496 下一个更大元素 I：多了张映射表

这道题给了两个数组 nums1 和 nums2，nums1 是 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，第三遍两三天后不看任何参考盲写，同时写出两种遍历方向，再顺手讲讲复杂度。达到这个标准之后，里面对单调栈的感觉基本就是肌肉记忆了，后面接雨水、最大矩形那些题，你会在某个瞬间突然发现：原来考点都是这题玩剩下的那套弹出结算逻辑。