LeetCode 第 739 题：每日温度（Daily Temperatures）

题目描述
给定一个整数数组 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. 初始化

   • 创建数组 answer，长度与 temperatures 相同，初始值全为 0。
   • 创建一个空栈 stack，用于存放数组索引（而不是温度值，因为索引可以同时获取温度值和计算天数差）。

2. 遍历温度数组

   • 对于每一天 i（从 0 到 n-1）：
     a. 检查栈是否为空且当前温度是否高于栈顶索引对应的温度：
     • 循环条件：栈非空 且 temperatures[i] > temperatures[stack[-1]]
     • 如果满足，说明当前温度 temperatures[i] 是栈顶元素的下一个更高温度。
       b. 计算天数差并更新答案：
     • 弹出栈顶索引 prev_index = stack.pop()
     • 计算天数差：answer[prev_index] = i - prev_index
       c. 将当前索引入栈：
     • 将当前索引 i 压入栈中，因为它的下一个更高温度可能还未出现。

3. 遍历结束后的处理

   • 栈中剩余元素的 answer 值保持为 0（因为后续没有更高温度），无需额外操作。

示例推导（以输入 [73,74,75,71,69,72,76,73] 为例）：

• i=0: 栈空，索引 0 入栈 → stack=[0]
• i=1: 温度 74 > 73（栈顶索引 0 对应温度），弹出 0，answer[0]=1-0=1；索引 1 入栈 → stack=[1]
• i=2: 温度 75 > 74，弹出 1，answer[1]=1；索引 2 入栈 → stack=[2]
• i=3: 温度 71 < 75，索引 3 入栈 → stack=[2,3]
• i=4: 温度 69 < 71，索引 4 入栈 → stack=[2,3,4]
• i=5: 温度 72 > 69，弹出 4，answer[4]=5-4=1；温度 72 > 71，弹出 3，answer[3]=5-3=2；温度 72 < 75，索引 5 入栈 → stack=[2,5]
• i=6: 温度 76 > 72，弹出 5，answer[5]=1；温度 76 > 75，弹出 2，answer[2]=6-2=4；栈空，索引 6 入栈 → stack=[6]
• i=7: 温度 73 < 76，索引 7 入栈 → stack=[6,7]
• 遍历结束，answer = [1,1,4,2,1,1,0,0]

复杂度分析

• 时间复杂度：O(n)，每个元素最多入栈和出栈一次。
• 空间复杂度：O(n)，栈的大小最大为 n。

关键点

• 单调栈适用于"寻找下一个更大/更小元素"类问题。
• 栈中存储索引，便于计算天数差和获取温度值。
• 栈内温度保持单调递减，确保每次出栈时都能正确计算距离。