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 暴力解法思路最直观的解法是使用双重循环外层循环遍历每一天的温度内层循环从当前天的下一天开始寻找第一个比当前温度高的天数计算天数差并存入结果数组如果遍历结束都没找到更高温度则存入0def dailyTemperatures(temperatures): n len(temperatures) answer [0] * n for i in range(n): for j in range(i1, n): if temperatures[j] temperatures[i]: answer[i] j - i break return answer时间复杂度O(n²) 空间复杂度O(1)不考虑输出数组3. 单调栈优化解法3.1 单调栈原理暴力解法存在大量重复比较可以使用单调栈来优化。单调栈是一种特殊的栈栈中的元素保持单调递增或递减的顺序。在这个问题中我们维护一个单调递减栈栈中存储的是温度的索引而非温度值本身当当前温度高于栈顶温度时弹出栈顶元素并计算天数差重复这个过程直到当前温度不大于栈顶温度将当前索引入栈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 实际应用场景股票分析计算买入后需要等待多少天股价会高于当前价格气象预测预测未来温度变化趋势商业决策商品价格波动分析5.2 题目变种下一个更大元素I给定两个数组找出第一个数组中每个元素在第二个数组中的下一个更大元素下一个更大元素II循环数组的情况柱状图中最大的矩形利用单调栈解决面积问题6. 代码优化与边界条件6.1 代码优化技巧使用enumerate简化索引访问预分配结果数组空间在栈中存储元组温度值索引可以避免多次数组访问优化后的代码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 answer6.2 边界条件处理空输入数组返回空数组所有温度相同返回全0数组温度单调递减返回全0数组温度单调递增返回[1,1,...,0]7. 不同语言实现对比7.1 Java实现public int[] dailyTemperatures(int[] temperatures) { int[] answer new int[temperatures.length]; StackInteger 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实现vectorint dailyTemperatures(vectorint temperatures) { vectorint answer(temperatures.size(), 0); stackint 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 常见错误栈中存储温度值而非索引导致无法计算天数差忘记处理栈中剩余元素其实不需要处理因为初始化时已经设为0边界条件处理不当如空输入或单元素输入8.2 调试技巧使用小测试用例手动模拟算法过程打印栈的状态和结果数组的变化过程对于特殊输入如全相同温度单独测试9. 算法可视化与理解为了更好地理解单调栈的工作过程我们可以用以下温度序列进行可视化 [73,74,75,71,69,72,76,73]处理过程初始空栈i0(73)入栈[0]i1(74)73弹出0answer[0]1-01入栈[1]i2(75)74弹出1answer[1]2-11入栈[2]i3(71)75入栈[2,3]i4(69)71入栈[2,3,4]i5(72)69弹出4answer[4]5-41 7271弹出3answer[3]5-32 7275停止入栈[2,5]i6(76)72弹出5answer[5]6-51 7675弹出2answer[2]6-24 栈空入栈[6]i7(73)76入栈[6,7]结束answer中未处理的位置保持010. 性能测试与对比我们使用Python的timeit模块对两种解法进行性能测试测试数据随机生成的10000个温度数据范围0-100结果暴力解法约12.5秒单调栈解法约0.05秒可以看出对于大规模数据单调栈解法优势非常明显。11. 进阶思考与扩展11.1 如何处理循环数组对于循环数组的情况即最后一个元素的下一个元素是第一个元素我们可以将数组扩展为原来的两倍使用取模运算模拟循环11.2 如何找出前面第一个更高的温度只需改变单调栈的单调方向维护单调递增栈和比较方向即可。11.3 如何找出温度变化的历史记录可以修改算法记录所有温度变化而不仅仅是第一个更高的温度。12. 实际工程应用建议在实际工程中应用此算法时考虑使用更节省空间的数据结构对于特别大的数据集可以考虑并行处理添加适当的日志和监控考虑使用更高效的编程语言实现核心算法13. 学习资源推荐《算法导论》- 基础算法理论LeetCode题库- 大量类似问题练习《编程珠玑》- 算法优化技巧GeeksforGeeks- 算法可视化与讲解14. 面试技巧与常见问题在面试中遇到此类问题时先明确问题要求确认输入输出从暴力解法开始分析复杂度逐步优化解释单调栈的原理讨论边界条件和特殊情况可以主动提出实际应用场景常见面试问题如何证明你的算法是正确的最坏情况下栈的空间复杂度是多少如何处理温度相同的情况如何修改算法来找到前面第一个更高的温度15. 个人经验分享在实际解决这个问题时我最初尝试了暴力解法但很快意识到其效率问题。通过绘制温度变化曲线我注意到可以利用历史信息来优化这引导我想到了单调栈的解法。在实现过程中最初我犯了在栈中存储温度值而非索引的错误导致无法正确计算天数差。通过添加详细的打印语句跟踪栈和结果数组的状态我最终找出了问题所在。一个实用的调试技巧是先用小规模的测试数据手动模拟算法过程确保理解正确后再处理大规模数据。另外在面试中解释算法时画图是非常有帮助的可以清晰地展示单调栈如何工作。 
长河君 · 2026/11/2 9:34:34 · 阅读 1.2k 单调栈算法解析：解决每日温度问题的高效方法
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 暴力解法思路最直观的解法是使用双重循环外层循环遍历每一天的温度内层循环从当前天的下一天开始寻找第一个比当前温度高的天数计算天数差并存入结果数组如果遍历结束都没找到更高温度则存入0def dailyTemperatures(temperatures): n len(temperatures) answer [0] * n for i in range(n): for j in range(i1, n): if temperatures[j] temperatures[i]: answer[i] j - i break return answer时间复杂度O(n²) 空间复杂度O(1)不考虑输出数组3. 单调栈优化解法3.1 单调栈原理暴力解法存在大量重复比较可以使用单调栈来优化。单调栈是一种特殊的栈栈中的元素保持单调递增或递减的顺序。在这个问题中我们维护一个单调递减栈栈中存储的是温度的索引而非温度值本身当当前温度高于栈顶温度时弹出栈顶元素并计算天数差重复这个过程直到当前温度不大于栈顶温度将当前索引入栈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 实际应用场景股票分析计算买入后需要等待多少天股价会高于当前价格气象预测预测未来温度变化趋势商业决策商品价格波动分析5.2 题目变种下一个更大元素I给定两个数组找出第一个数组中每个元素在第二个数组中的下一个更大元素下一个更大元素II循环数组的情况柱状图中最大的矩形利用单调栈解决面积问题6. 代码优化与边界条件6.1 代码优化技巧使用enumerate简化索引访问预分配结果数组空间在栈中存储元组温度值索引可以避免多次数组访问优化后的代码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 answer6.2 边界条件处理空输入数组返回空数组所有温度相同返回全0数组温度单调递减返回全0数组温度单调递增返回[1,1,...,0]7. 不同语言实现对比7.1 Java实现public int[] dailyTemperatures(int[] temperatures) { int[] answer new int[temperatures.length]; StackInteger 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实现vectorint dailyTemperatures(vectorint temperatures) { vectorint answer(temperatures.size(), 0); stackint 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 常见错误栈中存储温度值而非索引导致无法计算天数差忘记处理栈中剩余元素其实不需要处理因为初始化时已经设为0边界条件处理不当如空输入或单元素输入8.2 调试技巧使用小测试用例手动模拟算法过程打印栈的状态和结果数组的变化过程对于特殊输入如全相同温度单独测试9. 算法可视化与理解为了更好地理解单调栈的工作过程我们可以用以下温度序列进行可视化 [73,74,75,71,69,72,76,73]处理过程初始空栈i0(73)入栈[0]i1(74)73弹出0answer[0]1-01入栈[1]i2(75)74弹出1answer[1]2-11入栈[2]i3(71)75入栈[2,3]i4(69)71入栈[2,3,4]i5(72)69弹出4answer[4]5-41 7271弹出3answer[3]5-32 7275停止入栈[2,5]i6(76)72弹出5answer[5]6-51 7675弹出2answer[2]6-24 栈空入栈[6]i7(73)76入栈[6,7]结束answer中未处理的位置保持010. 性能测试与对比我们使用Python的timeit模块对两种解法进行性能测试测试数据随机生成的10000个温度数据范围0-100结果暴力解法约12.5秒单调栈解法约0.05秒可以看出对于大规模数据单调栈解法优势非常明显。11. 进阶思考与扩展11.1 如何处理循环数组对于循环数组的情况即最后一个元素的下一个元素是第一个元素我们可以将数组扩展为原来的两倍使用取模运算模拟循环11.2 如何找出前面第一个更高的温度只需改变单调栈的单调方向维护单调递增栈和比较方向即可。11.3 如何找出温度变化的历史记录可以修改算法记录所有温度变化而不仅仅是第一个更高的温度。12. 实际工程应用建议在实际工程中应用此算法时考虑使用更节省空间的数据结构对于特别大的数据集可以考虑并行处理添加适当的日志和监控考虑使用更高效的编程语言实现核心算法13. 学习资源推荐《算法导论》- 基础算法理论LeetCode题库- 大量类似问题练习《编程珠玑》- 算法优化技巧GeeksforGeeks- 算法可视化与讲解14. 面试技巧与常见问题在面试中遇到此类问题时先明确问题要求确认输入输出从暴力解法开始分析复杂度逐步优化解释单调栈的原理讨论边界条件和特殊情况可以主动提出实际应用场景常见面试问题如何证明你的算法是正确的最坏情况下栈的空间复杂度是多少如何处理温度相同的情况如何修改算法来找到前面第一个更高的温度15. 个人经验分享在实际解决这个问题时我最初尝试了暴力解法但很快意识到其效率问题。通过绘制温度变化曲线我注意到可以利用历史信息来优化这引导我想到了单调栈的解法。在实现过程中最初我犯了在栈中存储温度值而非索引的错误导致无法正确计算天数差。通过添加详细的打印语句跟踪栈和结果数组的状态我最终找出了问题所在。一个实用的调试技巧是先用小规模的测试数据手动模拟算法过程确保理解正确后再处理大规模数据。另外在面试中解释算法时画图是非常有帮助的可以清晰地展示单调栈如何工作。