单调栈算法解析：解决每日温度问题

1. 题目解析与核心思路

这道题来自经典的算法题库Hot100系列，编号739，题目名为"每日温度"。给定一个温度列表，要求返回一个列表，表示每一天需要等待多少天才能遇到更高的温度。如果没有更高的温度，则对应位置设为0。

举个例子： 输入：[73,74,75,71,69,72,76,73] 输出：[1,1,4,2,1,1,0,0]

1.1 问题本质分析

这实际上是一个典型的"下一个更大元素"问题的变种。我们需要为数组中的每个元素，找到它右边第一个比它大的元素，并记录两者之间的距离。

这类问题在现实中有很多应用场景：

• 股票价格分析（等待多少天后股价会高于当前）
• 气象数据分析（预测未来升温时间）
• 资源调度优化（等待资源满足需求的时间）

1.2 暴力解法分析

最直观的解法是双重循环：

def dailyTemperatures(T): n = len(T) res = [0] * n for i in range(n): for j in range(i+1, n): if T[j] > T[i]: res[i] = j - i break return res

时间复杂度O(n²)，空间复杂度O(1)。对于大规模数据（比如10^5量级）会超时。

2. 最优解：单调栈解法

2.1 单调栈原理

单调栈是一种特殊的栈结构，它保持栈内元素单调递增或单调递减。在这个问题中，我们使用单调递减栈：

• 栈中存储的是元素的索引（而不是值）
• 当新元素比栈顶元素大时，弹出栈顶元素并计算天数差
• 重复这个过程直到栈为空或栈顶元素大于等于当前元素
• 将当前元素索引入栈

2.2 完整实现代码

def dailyTemperatures(T): n = len(T) res = [0] * n stack = [] for i in range(n): while stack and T[i] > T[stack[-1]]: prev_index = stack.pop() res[prev_index] = i - prev_index stack.append(i) return res

2.3 复杂度分析

时间复杂度：O(n) - 每个元素最多入栈出栈一次 空间复杂度：O(n) - 最坏情况下所有元素都在栈中

3. 算法可视化与逐步推演

让我们用示例输入[73,74,75,71,69,72,76,73]来逐步推演：

初始化： stack = [] res = [0,0,0,0,0,0,0,0]

i=0, T[0]=73: stack = [0]

i=1, T[1]=74 > T[0]=73: res[0] = 1-0 = 1 stack = [1]

i=2, T[2]=75 > T[1]=74: res[1] = 2-1 = 1 stack = [2]

i=3, T[3]=71 < T[2]=75: stack = [2,3]

i=4, T[4]=69 < T[3]=71: stack = [2,3,4]

i=5, T[5]=72 > T[4]=69: res[4] = 5-4 = 1 stack = [2,3]

T[5]=72 > T[3]=71: res[3] = 5-3 = 2 stack = [2]

T[5]=72 < T[2]=75: stack = [2,5]

i=6, T[6]=76 > T[5]=72: res[5] = 6-5 = 1 stack = [2]

T[6]=76 > T[2]=75: res[2] = 6-2 = 4 stack = [6]

i=7, T[7]=73 < T[6]=76: stack = [6,7]

最终结果：[1,1,4,2,1,1,0,0]

4. 变种与扩展问题

4.1 类似题目

• 496.下一个更大元素I
• 503.下一个更大元素II（循环数组）
• 901.股票价格跨度

4.2 实际应用扩展

1. 电商价格预测：预测某商品价格何时会高于当前价
2. 服务器负载监控：预测何时负载会超过当前水平
3. 交通流量分析：预测何时车流量会超过当前值

5. 常见错误与调试技巧

5.1 常见错误

1. 栈中存储值而非索引：会导致无法计算天数差
2. 忘记处理栈中剩余元素：这些位置的结果应该保持为0
3. 边界条件处理：空输入或单元素输入的情况

5.2 调试技巧

1. 打印栈状态：在每次循环后打印栈内容
2. 小规模测试：先用3-5个元素的简单案例验证
3. 可视化推演：像第3节那样手动推演过程

6. 性能优化与语言特性

6.1 Python优化技巧

1. 使用预分配结果的列表
2. 避免不必要的列表操作
3. 考虑使用collections.deque作为栈（虽然在这个问题中提升不大）

6.2 其他语言实现

Java版本：

public int[] dailyTemperatures(int[] T) { int[] res = new int[T.length]; Deque<Integer> stack = new ArrayDeque<>(); for (int i = 0; i < T.length; i++) { while (!stack.isEmpty() && T[i] > T[stack.peek()]) { int prev = stack.pop(); res[prev] = i - prev; } stack.push(i); } return res; }

7. 复杂度证明与数学分析

7.1 时间复杂度证明

每个元素最多被压入栈一次、弹出栈一次，因此内层while循环的总次数不会超过2n次，整体时间复杂度为O(n)。

7.2 空间复杂度分析

最坏情况下（单调递减输入），所有元素都会被压入栈，空间复杂度为O(n)。

8. 实际工程应用建议

1. 大数据处理：当处理海量温度数据时，可以考虑分块处理
2. 实时系统：可以维护一个滑动窗口的单调栈
3. 分布式计算：可以将数据分区，分别计算后合并结果

9. 面试技巧与答题思路

9.1 面试回答框架

1. 先说明暴力解法及其缺点
2. 引入单调栈的概念
3. 详细解释算法步骤
4. 分析时间/空间复杂度
5. 讨论可能的优化和变种

9.2 白板编程技巧

1. 先写出清晰的函数签名
2. 注释算法关键步骤
3. 用示例数据验证
4. 考虑边界条件处理

10. 学习资源推荐

1. 《算法导论》中的栈和队列章节
2. LeetCode单调栈专题
3. 可视化算法学习网站：VisuAlgo
4. 经典教材：《算法4》中的相关章节

这个算法虽然代码简洁，但包含了栈的高级应用思想。建议通过反复练习类似题目来掌握单调栈的应用模式。在实际编程中，要注意栈中存储的是索引还是值，这是容易出错的关键点。