暴力到O(n)的经典优化)
1. 题目场景与暴力思路
1.1 题目描述和示例
先说题目本身。“每日温度”是单调栈专题里最经典的一道入门题，几乎每个接触单调栈的人都会先拿它开刀。题目是这样的：给你一个数组temperatures，记录的是连续若干天的每日温度，让你返回一个等长的数组answer，其中answer[i]表示：从第i天往后，需要等多少天才能等到一个比当天温度更高的温度；如果之后都不存在更高的温度，则该位置填0。
举个例子：
temperatures = [73, 74, 75, 71, 69, 72, 76, 73]输出应该是：
[1, 1, 4, 2, 1, 1, 0, 0]怎么理解这个输出？第 0 天温度 73，第 1 天温度 74 就比 73 高了，所以等 1 天；第 1 天温度 74，第二天 75 就更高，所以也是 1；第 2 天温度 75，往后看 71、69、72、76，直到第 6 天才出现 76，中间隔了 4 天，所以填 4；最后两天分别是 76 和 73，之后没有更高的温度了，就填 0。
这种题目属于典型的“下一个更大元素”变种，只不过它要求的是距离而不是元素本身的值。很多初学者第一反应都是暴力双层循环，我也一样，毕竟题目看起来简单：对每一个位置，往后扫一遍找更大的数，找到就记录距离，找不到就记 0。
1.2 暴力解法为什么不够用
暴力解法确实能过小数据，写起来也直白：
def dailyTemperatures(temperatures): n = len(temperatures) res = [0] * n for i in range(n): for j in range(i + 1, n): if temperatures[j] > temperatures[i]: res[i] = j - i break return res两层循环，外层遍历每一天，内层从下一天开始找更高温度，一旦找到就跳出。时间复杂度是 O(n²)，最坏情况下温度数组是严格递减的，比如[5, 4, 3, 2, 1]，那么内层循环要一直扫到结尾都找不到更大的，总共会执行差不多 n²/2 次比较。
真正的问题在这里：如果 n 是几千，暴力没问题；但当 n 到了十万、百万量级，O(n²) 就完全扛不住了。力扣上这道题的数据范围是n <= 10^5，O(n²) 的算法直接超时。所以我们需要一种更聪明的办法，把时间复杂度降到 O(n)。
2. 单调栈的引入与核心原理
2.1 单调栈的本质与特性
单调栈，说白了就是栈内元素保持单调性的栈。什么叫单调？要么从栈底到栈顶元素持续递增（单调递增栈），要么持续递减（单调递减栈）。注意这里的单调性通常指的是元素值的大小，但在很多题目里，栈内存的是下标，比较的是下标对应的值，这个细节非常关键，后面我会重点讲。
单调栈并不是一种新的数据结构，它不是栈的增强版本，而是一种对栈的使用策略。它的核心思想是：
在遍历数组的过程中，让栈内元素始终保持单调性，同时利用出栈这个动作去“结算”当前栈顶元素的信息。
为什么这种策略有用？因为我们往往需要知道“当前元素左边/右边第一个比它大/小的元素在哪”，而单调栈可以在一次遍历中，既找到左边信息又找到右边信息（依据遍历方向和出栈时机）。
用生活化的方式来理解。想象一排人站队，每个人都想知道：站在我右手边，比我高且离我最近的人是谁？如果从队伍最左边开始一个一个处理，用栈来维护一个“身高从高到低排列”的候选队列，那么每当新来一个人，他可以把那些比自己矮的人“挡住”，那些矮个子就出栈，并且在出栈的那一刻可以结算出答案。这个类比在“每日温度”里非常贴合：温度升高的过程就像队伍里冒出一个更高的人，把之前那些“矮温度”全部“挡住”并给出等待天数。
2.2 从“每日温度”看单调栈的运作方式
回到题目。我们要找的是“右边第一个比自己大的元素”，所以应该维护一个单调递减栈。也就是说，栈内从栈底到栈顶，温度值应该是递减的。为什么是递减？因为我们想快速知道当前正在处理的元素，会不会是栈顶元素等待的那个“更高温度”。如果当前元素比栈顶元素对应的温度高，那么栈顶元素就可以出栈并结算答案了。
举例推演一遍。假设温度数组是[73, 74, 75, 71, 69, 72, 76, 73]。我们用栈存下标，初始栈为空：
- 处理第 0 天（73）：栈为空，下标 0 入栈。此时栈内：
[0]。 - 处理第 1 天（74）：温度 74 比栈顶下标 0 对应的温度 73 更高，所以下标 0 出栈，并记录
res[0] = 1 - 0 = 1。然后下标 1 入栈。栈内：[1]。 - 处理第 2 天（75）：75 比栈顶对应的 74 更高，下标 1 出栈，
res[1] = 1。下标 2 入栈。栈内：[2]。 - 处理第 3 天（71）：71 比栈顶 75 低，不满足“更高”，所以不出栈，下标 3 入栈。栈内：
[2, 3]。 - 处理第 4 天（69）：69 比栈顶 71 低，下标 4 入栈。栈内：
[2, 3, 4]。 - 处理第 5 天（72）：72 比栈顶下标 4 对应的 69 高，下标 4 出栈，
res[4] = 1；再比栈顶下标 3 对应的 71 高，下标 3 出栈，res[3] = 5 - 3 = 2；再比栈顶下标 2 对应的 75 低，停止出栈。然后下标 5 入栈。栈内：[2, 5]。 - 处理第 6 天（76）：76 比 72 高，下标 5 出栈，
res[5] = 1；再比 75 高，下标 2 出栈，res[2] = 6 - 2 = 4。栈空，下标 6 入栈。栈内：[6]。 - 处理第 7 天（73）：73 比 76 低，入栈。栈内：
[6, 7]。
最后栈里剩下的下标 6 和 7，说明它们后面没有更高的温度，答案保持 0。
整个过程非常流畅：每个元素最多入栈一次、出栈一次，所以时间复杂度是 O(n)。出栈的时候，栈顶元素刚好找到了“右边第一个比它大”的元素，所以答案可以在出栈时精确计算。
3. 代码实现与关键细节
3.1 Python 实现与逐行解读
直接给一份完整可跑的 Python 代码：
def dailyTemperatures(temperatures): n = len(temperatures) res = [0] * n stack = [] for i in range(n): # 当前温度比栈顶温度高，结算栈顶下标的答案 while stack and temperatures[i] > temperatures[stack[-1]]: idx = stack.pop() res[idx] = i - idx stack.append(i) return res逐行拆开看：
res = [0] * n：结果数组，先全部初始化为 0，最后留在栈里的元素默认就是 0。stack = []：用来存下标，不是温度值。- 在循环内使用
while而不是if，这点很重要。因为当前温度可能比栈里多个元素都高，需要把每一个符合条件的栈顶都弹出并结算。比如第 5 天温度 72，它同时干掉了 69 和 71 两个栈顶元素。 temperatures[stack[-1]]是栈顶下标对应的温度。注意我们比较的是温度值，但栈里存的是下标，因为最后计算距离要用下标的差值。
判断条件while stack and temperatures[i] > temperatures[stack[-1]]保证栈内温度从栈底到栈顶严格递减。如果出现相等的情况怎么办？题目要求的是“更高温度”，温度相等时不算更高，所以我们用>而不是>=，相等时新元素不会弹掉旧元素，而是直接入栈。这样能保证相等温度的日子里，前面的日子要等后面真正更高的温度，而不是把相等的日子当作答案。
3.2 为什么栈里存的是下标而不是温度值
这是新手最容易踩的坑，也是很多老手讲不清楚的地方。我当初第一次自己实现时，直接把温度值放进栈里，结果计算答案时发现怎么都算不出距离，只能干瞪眼。后来才明白，我们需要的是“从当前天数到下一天数之间隔了多少天”，这就需要同时知道两个下标：当前遍历到的i和栈顶元素的下标idx。如果栈里只存温度值，确实可以判断出“栈顶温度比当前温度小”，但出栈后你根本不知道这个温度是第几天的，res该更新到哪个位置？所以必须存下标。
栈内存下标，比较时通过下标去数组里取值，这是单调栈题目的通用范式。不只是“每日温度”，几乎所有“下一个更大/更小元素”的题目都遵循这个模式：栈内维护的是候选位置，通过位置能访问值，也能计算位置距离。
另外注意，在 Python 中列表充当栈，stack[-1]是栈顶，stack.pop()弹出并返回栈顶，stack.append(i)入栈。这些 API 都是 O(1) 的，不用担心性能问题。
4. 复杂度分析与可优化方向
4.1 时间复杂度和空间复杂度分析
先说时间复杂度。每个下标只会入栈一次，也只会出栈最多一次。在整个循环过程中，while循环的总执行次数等于所有元素出栈次数的总和，不会超过 n。所以加上外层循环 n 次，总体操作次数是 O(n) 级别。这个结论很多人可以背下来，但真正理解它你需要意识到：一个元素一旦出栈，就再也不会被处理了，所以虽然内层看着有 while 循环，但所有 while 循环的总执行量是 n，不是 n²。
空间复杂度方面，最坏情况是温度数组严格递减，例如[5, 4, 3, 2, 1]，此时每一天的温度都比前一天低，永远不会有元素出栈，栈内会堆积全部 n 个下标，所以空间复杂度是 O(n)。平均情况可能小一点，但最坏情况必须按 O(n) 来分析。
4.2 空间优化思路：数组模拟栈
如果对性能吹毛求疵，可以用数组模拟栈来避免 Python 列表的动态扩容开销。思路是预分配一个长度为 n 的数组stack，再用一个指针top表示栈顶位置，初始为 -1 表示空栈。入栈操作就是top += 1; stack[top] = i；出栈操作就是top -= 1；查看栈顶就是stack[top]。
写成代码：
def dailyTemperatures(temperatures): n = len(temperatures) res = [0] * n stack = [0] * n top = -1 for i in range(n): while top >= 0 and temperatures[i] > temperatures[stack[top]]: idx = stack[top] top -= 1 res[idx] = i - idx top += 1 stack[top] = i return res这种写法在模拟环境中稍微复杂一点，但优点是没有对象方法调用，也没有列表扩容的额外开销。实际刷题时，Python 原生列表作为栈已经足够快，除非是极高压的 10^6 量级数据，否则不必刻意如此。不过理解数组模拟栈的思路，对理解单调栈底层实现是有帮助的。
另外有人可能会想，能不能倒序遍历数组，用从右往左的方式省掉栈？其实有一个变体：从右往左遍历，维护一个单调递增栈（栈底到栈顶递增），每次找右边第一个比当前大的元素，这样也可以做到 O(n)，而且思路更直觉一些。代码例如：
def dailyTemperatures(temperatures): n = len(temperatures) res = [0] * n stack = [] for i in range(n - 1, -1, -1): while stack and temperatures[i] >= temperatures[stack[-1]]: stack.pop() res[i] = stack[-1] - i if stack else 0 stack.append(i) return res这个方向是从右往左，每次把当前元素与栈顶比较，如果栈顶温度不大于当前温度，就弹出，因为那些更小或相等的温度不可能是当前元素的“下一个更高温度”的答案（它们已经被当前温度挡住）。弹完以后，如果栈非空，栈顶就是右边第一个比当前温度大的元素，直接算距离。这种写法在逻辑上更贴近“寻找右边第一个更大元素”的定义，但要注意判断条件是>=，因为相等温度不算更大，需要弹出相等的元素，让栈里保留严格大于当前元素的值。
两种思路都能 AC，我更推荐第一种从左往右的写法，因为它是单调栈最标准的“结算”模式，在后续学习其他单调栈题目时更容易迁移。
5. 常见问题与排查技巧
5.1 常见错误速查表
我把自己在学习和教学中遇到的高频错误整理成一个表格，方便对照自查：
| 错误类型 | 错误表现 | 原因 | 正确做法 |
|---|---|---|---|
| 栈内存值 | 结果全是 0 或计算不正确 | 存了温度值后无法得到下标，无法计算距离 | 栈内存下标，比较时用temperatures[stack[-1]] |
使用if代替while | 部分较小温度没有被弹出 | 当前温度可能大于多个栈顶元素 | 使用while循环持续弹出 |
| 判断条件用错 | 结果偏大或偏小 | 应该是>时弹出，相等时不弹出；另一方向则相反 | 从左往右用>；从右往左用>= |
答案初始化为-1 | 输出包含负数 | 题目要求无更高温度时填 0 | 初始化为 0 |
| 混淆栈的单调方向 | 栈内温度顺序不对 | 找“下一个更大”要用递减栈，找“下一个更小”要用递增栈 | 牢记：找更大，栈内递减；找更小，栈内递增 |
5.2 边界情况与特殊输入
- 空数组：此时直接返回空数组。代码里
n=0，循环不执行，返回[]，没问题。 - 单元素数组：只有一个温度，后面没有更高温度，结果自然是
[0]。代码中栈会直接放进去，循环结束，返回[0]。 - 严格递减数组：例如
[30, 20, 10]。从左往右版本里，每个新温度都小于等于栈顶，所以不出栈，全部入栈，答案全为 0。从右往左版本里，处理到索引 0 时栈内可能有更大的元素，但因为都不比 30 大？其实 30 是最高的，所以最终也是 0。两种都正确。 - 严格递增数组：
[10, 20, 30]。从左往右版本，每次新温度都会把前一个栈顶弹出，答案都是 1。注意这里每个位置等待 1 天即可。 - 存在相等温度：
[70, 70, 80]。从左往右版本，第二个 70 不会弹出栈顶的 70，因为不满足>，所以第二个 70 会入栈，栈内两个下标温度都为 70，严格递减的顺序被破坏了？严格递减要求每个元素都不大于前一个，允许相等吗？严格递减通常不允许相等，但我们的判断条件是>才弹出，等于时不弹出，所以栈内可能有两个相邻的温度相等，这就不是“严格递减”了，而是“非递增”。但这不影响正确性，因为我们要找的是“更高温度”，相等的温度不能作为答案。从右往左版本用>=则会弹出相等的栈顶，这样栈内保持严格递增，也能得到正确结果。所以要注意，单调栈的“单调”在实际代码中可能是非严格单调，具体看题目要求。
还有一个常见的疑问：为什么从右往左的版本要用>=？因为如果只用>，那么遇到相等的温度时，右边的相等温度不会弹出，它就会一直留在栈里，导致当前元素在计算“下一个更高温度”时，可能会错误地跳到那个相等温度后面更远的更大温度？其实不会错，因为相等的温度不会被当作答案，但留着它会导致栈里存在冗余信息。用>=弹出相等元素，让栈里只保留严格更大的候选者，逻辑更干净。
6. 单调栈的进阶应用与识别套路
6.1 单调栈的变式题型
“每日温度”只是单调栈的引子。一旦你把这套“入栈、出栈、结算”的流程吃透，你会发现大量题目都是在做同样的事，只是把“温度”换成了别的值，把“距离”换成了别的信息。
典型的变式有：
- 下一个更大元素 I / II / III：给一个数组，求每个元素右边第一个比它大的元素值，而不是距离。做法几乎一样，只是出栈时记录栈顶元素的答案是
nums[i]而不是i - idx。循环数组的情况可以用“拼接两倍数组”或“模运算”来处理。 - 每日温度本身就是“下一个更大元素”的距离版。
- 接雨水：给定柱状图高度，求能接多少雨水。这题需要同时从左和右找更高的柱子，单调栈的做法是维护一个递减栈，遇到比栈顶高的柱子时，利用中间弹出来的一层计算横向积水面积。这里的结算逻辑比“每日温度”复杂一点，但核心的单调栈思想一致。
- 柱状图中最大的矩形：找每个柱子左边第一个比它矮和右边第一个比它矮的位置，就能算出以该柱子为高的最大矩形宽度。这需要用单调递增栈。
- 去除重复字母 / 移掉 K 位数字：这些看似和“更大元素”无关，但本质上是利用单调栈维护最小字典序或最大数，也符合“栈内保持某种极值”的思想。
所以单调栈并不是一个孤立的技巧，它是“下一个更大/更小元素”问题的标准解法，而这一类问题在面试和实际开发里经常出现，比如股票价格回测、日志时间序列分析、滑动窗口极值维护等场景，都有它的影子。
6.2 怎么判断一道题能不能用单调栈
我总结了一个比较实用的判断方法，供你参考：
- 题目中出现了“下一个更大”“下一个更小”“左边第一个更小”“右边第一个更大”等字眼，大概率就是单调栈。
- 需要在一个序列中，对每个元素找某个方向的最近极值关系，并且遍历过程中信息存在“滞后结算”的特性。
- 暴力解法是 O(n²)，而数据规模在 10^5 以上，需要优化到 O(n) 或 O(n log n)。
- 没有需要维护的复合结构，比如区间最大值、动态更新等，如果是那些，可能要配合线段树或堆。
但要注意，不是所有“找更大元素”都只用单调栈。比如要求“跳跃游戏”中每个位置能跳到的最远位置，或者“在线”查询某个区间的下一个更大值，可能还需要离线处理或者配合其他数据结构。单调栈是一个很强的工具，但不要滥用。
6.3 个人实践建议
最后说一点我的实际体会。刚开始学单调栈时，我不是很理解为什么栈里存下标，总是背模板，但一遇到变式就懵。后来我换了一个方法：每次做题，先不要写代码，只用手工推演一遍“每日温度”的流程，把栈的变化、出栈时机、答案更新步骤写在纸上。推演三遍以后，我就能在不看模板的情况下写出来了。这个方法真的很有效。
另外，如果你在刷题，建议把“每日温度”和“下一个更大元素”放在一起刷，互相参照。你会发现它们本质是同一个解法，只是结算时记录的东西不同。然后把“柱状图中最大的矩形”也放进来，体会单调栈在更复杂环境中的用法，这样对整个数据结构的能力边界会理解得更深。
再分享一个小技巧：写单调栈题的时候，在循环里加一个print(stack)调试，看栈的变化是否符合预期。很多人觉得调试很麻烦，但其实对于单调栈这种逻辑，肉眼跟踪栈的变化比看变量值更直观。我常常在while循环前后打印栈的内容，一旦发现栈里的温度没有保持预期的单调性，就能立刻定位问题是判断条件写反了，还是相等情况的处理不对。
如果你现在正卡在单调栈的入门阶段，不要急。这类题目逻辑比较绕，但题目类型非常有限，多做几道经典题，把出栈结算的时机彻底吃透，你会发现之后再遇到同类题，基本就是秒杀。
