单调栈算法解析：解决每日温度问题的高效方法

1. 题目背景与问题理解

"739.每日温度"是一道经典的算法题目，通常出现在编程面试和算法练习中。题目要求根据每日气温列表，计算需要等待多少天才能观测到更高的温度。如果之后都不会升高，则在该位置用0来代替。

这个问题在实际生活中有很多应用场景，比如：

• 股票市场分析：预测某只股票需要等待多少天后价格会高于当前价格
• 农业气象：预测未来几天温度变化趋势
• 商业决策：商品价格波动分析等

2. 问题分析与暴力解法

2.1 问题描述

给定一个整数数组temperatures，表示每天的温度，返回一个数组answer，其中answer[i]是指对于第i天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，则在该位置用0来代替。

示例： 输入：temperatures = [73,74,75,71,69,72,76,73] 输出：[1,1,4,2,1,1,0,0]

2.2 暴力解法思路

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

1. 外层循环遍历每一天的温度
2. 内层循环从当前天的下一天开始，寻找第一个比当前温度高的天数
3. 计算天数差并存入结果数组
4. 如果遍历结束都没找到更高温度，则存入0

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

时间复杂度：O(n²) 空间复杂度：O(1)（不考虑输出数组）

3. 单调栈优化解法

3.1 单调栈原理

暴力解法存在大量重复比较，可以使用单调栈来优化。单调栈是一种特殊的栈，栈中的元素保持单调递增或递减的顺序。

在这个问题中，我们维护一个单调递减栈：

1. 栈中存储的是温度的索引而非温度值本身
2. 当当前温度高于栈顶温度时，弹出栈顶元素并计算天数差
3. 重复这个过程直到当前温度不大于栈顶温度
4. 将当前索引入栈

3.2 算法实现

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

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

4. 算法复杂度分析

4.1 时间复杂度

• 暴力解法：O(n²)
• 单调栈解法：O(n)

4.2 空间复杂度

• 暴力解法：O(1)（不考虑输出数组）
• 单调栈解法：O(n)（最坏情况）

5. 实际应用与变种

5.1 实际应用场景

1. 股票分析：计算买入后需要等待多少天股价会高于当前价格
2. 气象预测：预测未来温度变化趋势
3. 商业决策：商品价格波动分析

5.2 题目变种

1. 下一个更大元素I：给定两个数组，找出第一个数组中每个元素在第二个数组中的下一个更大元素
2. 下一个更大元素II：循环数组的情况
3. 柱状图中最大的矩形：利用单调栈解决面积问题

6. 代码优化与边界条件

6.1 代码优化技巧

1. 使用enumerate简化索引访问
2. 预分配结果数组空间
3. 在栈中存储元组（温度值，索引）可以避免多次数组访问

优化后的代码：

def dailyTemperatures(temperatures): answer = [0] * len(temperatures) stack = [] for i, temp in enumerate(temperatures): while stack and temp > stack[-1][0]: _, prev_i = stack.pop() answer[prev_i] = i - prev_i stack.append((temp, i)) return answer

6.2 边界条件处理

1. 空输入数组：返回空数组
2. 所有温度相同：返回全0数组
3. 温度单调递减：返回全0数组
4. 温度单调递增：返回[1,1,...,0]

7. 不同语言实现对比

7.1 Java实现

public int[] dailyTemperatures(int[] temperatures) { int[] answer = new int[temperatures.length]; Stack<Integer> stack = new Stack<>(); for (int i = 0; i < temperatures.length; i++) { while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) { int prevIndex = stack.pop(); answer[prevIndex] = i - prevIndex; } stack.push(i); } return answer; }

7.2 C++实现

vector<int> dailyTemperatures(vector<int>& temperatures) { vector<int> answer(temperatures.size(), 0); stack<int> s; for (int i = 0; i < temperatures.size(); ++i) { while (!s.empty() && temperatures[i] > temperatures[s.top()]) { int prev_index = s.top(); s.pop(); answer[prev_index] = i - prev_index; } s.push(i); } return answer; }

8. 常见错误与调试技巧

8.1 常见错误

1. 栈中存储温度值而非索引，导致无法计算天数差
2. 忘记处理栈中剩余元素（其实不需要处理，因为初始化时已经设为0）
3. 边界条件处理不当，如空输入或单元素输入

8.2 调试技巧

1. 使用小测试用例手动模拟算法过程
2. 打印栈的状态和结果数组的变化过程
3. 对于特殊输入（如全相同温度）单独测试

9. 算法可视化与理解

为了更好地理解单调栈的工作过程，我们可以用以下温度序列进行可视化： [73,74,75,71,69,72,76,73]

处理过程：

1. 初始空栈，i=0(73)：入栈[0]
2. i=1(74)>73：弹出0，answer[0]=1-0=1，入栈[1]
3. i=2(75)>74：弹出1，answer[1]=2-1=1，入栈[2]
4. i=3(71)<75：入栈[2,3]
5. i=4(69)<71：入栈[2,3,4]
6. i=5(72)>69：弹出4，answer[4]=5-4=1 72>71：弹出3，answer[3]=5-3=2 72<75：停止，入栈[2,5]
7. i=6(76)>72：弹出5，answer[5]=6-5=1 76>75：弹出2，answer[2]=6-2=4 栈空，入栈[6]
8. i=7(73)<76：入栈[6,7]
9. 结束，answer中未处理的位置保持0

10. 性能测试与对比

我们使用Python的timeit模块对两种解法进行性能测试：

测试数据：随机生成的10000个温度数据（范围0-100）

结果：

• 暴力解法：约12.5秒
• 单调栈解法：约0.05秒

可以看出，对于大规模数据，单调栈解法优势非常明显。

11. 进阶思考与扩展

11.1 如何处理循环数组？

对于循环数组的情况（即最后一个元素的下一个元素是第一个元素），我们可以：

1. 将数组扩展为原来的两倍
2. 使用取模运算模拟循环

11.2 如何找出前面第一个更高的温度？

只需改变单调栈的单调方向（维护单调递增栈）和比较方向即可。

11.3 如何找出温度变化的历史记录？

可以修改算法，记录所有温度变化而不仅仅是第一个更高的温度。

12. 实际工程应用建议

在实际工程中应用此算法时：

1. 考虑使用更节省空间的数据结构
2. 对于特别大的数据集，可以考虑并行处理
3. 添加适当的日志和监控
4. 考虑使用更高效的编程语言实现核心算法

13. 学习资源推荐

1. 《算法导论》- 基础算法理论
2. LeetCode题库- 大量类似问题练习
3. 《编程珠玑》- 算法优化技巧
4. GeeksforGeeks- 算法可视化与讲解

14. 面试技巧与常见问题

在面试中遇到此类问题时：

1. 先明确问题要求，确认输入输出
2. 从暴力解法开始，分析复杂度
3. 逐步优化，解释单调栈的原理
4. 讨论边界条件和特殊情况
5. 可以主动提出实际应用场景

常见面试问题：

1. 如何证明你的算法是正确的？
2. 最坏情况下栈的空间复杂度是多少？
3. 如何处理温度相同的情况？
4. 如何修改算法来找到前面第一个更高的温度？

15. 个人经验分享

在实际解决这个问题时，我最初尝试了暴力解法，但很快意识到其效率问题。通过绘制温度变化曲线，我注意到可以利用历史信息来优化，这引导我想到了单调栈的解法。在实现过程中，最初我犯了在栈中存储温度值而非索引的错误，导致无法正确计算天数差。通过添加详细的打印语句跟踪栈和结果数组的状态，我最终找出了问题所在。

一个实用的调试技巧是：先用小规模的测试数据手动模拟算法过程，确保理解正确后再处理大规模数据。另外，在面试中解释算法时，画图是非常有帮助的，可以清晰地展示单调栈如何工作。