LeetCode 第 739 题：每日温度 题目描述 给定一个整数数组 temperatures ，表示每天的温度。你需要返回一个数组 answer ，其中 answer[i] 是指在第 i 天之后，要等多少天才能遇到一个更温暖的温度。如果未来没有更温暖的日子，则 answer[i] 为 0。 例如： 输入：temperatures = [ 73,74,75,71,69,72,76,73 ] 输出：[ 1,1,4,2,1,1,0,0 ] 解题过程 1. 问题理解 我们需要为每一天找到下一个比它温度更高的日子出现在几天后。这可以转化为：对于数组中的每个元素，找到其右边第一个比它大的元素，计算两者索引的差值。 2. 暴力解法（基础思路） 最直接的方法是使用双重循环： 外层循环遍历每一天 i 内层循环从 i+1 开始向后扫描，找到第一个 temperatures[ j] > temperatures[ i ] 的 j answer[ i ] = j - i 时间复杂度：O(n²)，在数据量大时会超时。 3. 优化思路：单调栈 观察发现，当我们向后扫描时，有些天的温度信息可以被重复利用。比如一个高温日可能同时是前面多个低温日的"下一个更暖日"。 我们可以使用 单调递减栈 来优化： 栈中存放的是 索引 （这样既能比较温度又能计算天数差） 栈从底到顶对应的温度值是递减的（保证栈的单调性） 当遇到比栈顶温度高的日子时，说明找到了栈顶那天的"下一个更暖日" 4. 算法步骤详解 初始化一个空栈 stack 和结果数组 answer（初始化为全0） 遍历每一天 i（从0到n-1）： 当栈不为空且当前温度 temperatures[ i ] > 栈顶那天的温度时： 弹出栈顶元素 top（这是等待更暖温度的那天） 计算天数差：answer[ top ] = i - top 将当前天 i 入栈 遍历结束后，栈中剩余的天数都是没有更暖温度的，保持 answer 为0 5. 具体示例分析 以 temperatures = [ 73,74,75,71,69,72,76,73 ] 为例： i=0(73°): 栈空，入栈 → stack=[ 0 ] i=1(74°): 74>73，弹出0，answer[ 0]=1-0=1；入栈1 → stack=[ 1 ] i=2(75°): 75>74，弹出1，answer[ 1]=2-1=1；入栈2 → stack=[ 2 ] i=3(71°): 71<75，入栈 → stack=[ 2,3 ] i=4(69°): 69<71，入栈 → stack=[ 2,3,4 ] i=5(72°): 72>69，弹出4，answer[ 4]=5-4=1；72>71，弹出3，answer[ 3]=5-3=2；入栈5 → stack=[ 2,5 ] i=6(76°): 76>72，弹出5，answer[ 5]=6-5=1；76>75，弹出2，answer[ 2]=6-2=4；入栈6 → stack=[ 6 ] i=7(73°): 73<76，入栈 → stack=[ 6,7 ] 剩余栈中元素没有更暖温度，answer保持0。 6. 复杂度分析 时间复杂度：O(n)，每个元素最多入栈出栈一次 空间复杂度：O(n)，最坏情况下栈的大小为n 7. 关键点总结 单调栈维护的是"尚未找到更暖温度"的日子的索引 栈的单调递减保证了当遇到高温时，可以一次性解决多个等待的日子 这种方法将看似O(n²)的问题优化到了O(n)