LeetCode 第 739 题：每日温度（Daily Temperatures） 题目描述 给定一个整数数组 temperatures ，表示每天的温度。你需要返回一个数组 answer ，其中 answer[i] 是指在第 i 天之后，要等多少天才能遇到一个更暖和的温度。如果未来没有更暖和的日子，则在该位置放入 0 。 示例： 输入：temperatures = [ 73,74,75,71,69,72,76,73 ] 输出：[ 1,1,4,2,1,1,0,0 ] 解题思路 这个问题可以理解为：对于数组中的每个元素，找到它右边第一个比它大的元素，并计算两者之间的距离。 方法一：暴力解法（不通过，但有助于理解） 对每一天 i ，向后扫描每一天 j ，直到找到第一个温度更高的日子，则 answer[i] = j - i 。 时间复杂度 O(n²)，在数据量大时会超时。 方法二：单调栈（最优解） 核心思想是维护一个栈，栈中存放的是数组的索引，这些索引对应的温度值是单调递减的。这样，当我们遇到一个比栈顶温度高的天数时，就可以一次性更新多个结果。 步骤详解 初始化一个空栈 stack 和一个结果数组 answer ，长度与输入相同，初始值全为 0 。 遍历每一天的温度（使用索引 i 从 0 到 n-1 ）： a. 循环判断 ：检查栈是否非空，并且当前温度 temperatures[i] 是否大于栈顶索引 index 对应的温度 temperatures[stack[-1]] 。 如果是，说明我们找到了栈顶元素的下一个更高温度日。 弹出栈顶元素 topIndex = stack.pop() 。 计算等待天数： answer[topIndex] = i - topIndex 。 继续循环，将当前温度与新的栈顶元素比较（因为栈是递减的，当前高温可能也是栈中多个元素的下一个高温）。 b. 压入当前索引 ：将当前天的索引 i 压入栈中。这一步保证了栈内的索引对应的温度是单调递减的。 遍历结束后，栈中可能还剩一些索引。这些索引代表它们后面没有更高的温度了。由于我们的 answer 数组初始化为 0 ，所以这些位置的结果已经是 0 ，无需额外处理。 为什么单调栈有效？ 栈中保存的是“尚未找到下一个更暖天”的日期索引。 由于我们按顺序遍历，并且只将温度递减的日期索引入栈，所以当遇到一个高温时，它一定是栈中所有比它低的温度的“下一个更高温度”。 这个过程确保了每个元素只入栈和出栈一次，时间复杂度为 O(n)。 示例推演 以输入 [73,74,75,71,69,72,76,73] 为例： i=0 (73°): 栈空，索引0入栈。栈: [ 0 ] i=1 (74°): 74 > 73 (栈顶索引0的温度)。弹出0，answer[ 0] = 1-0 = 1。栈空，索引1入栈。栈: [ 1 ] i=2 (75°): 75 > 74。弹出1，answer[ 1] = 2-1 = 1。栈空，索引2入栈。栈: [ 2 ] i=3 (71°): 71 < 75，索引3入栈。栈: [ 2, 3 ] i=4 (69°): 69 < 71，索引4入栈。栈: [ 2, 3, 4 ] i=5 (72°): 72 > 69。弹出4，answer[ 4] = 5-4 = 1。栈顶变3 (71°)，72 > 71。弹出3，answer[ 3] = 5-3 = 2。栈顶变2 (75°)，72 < 75，停止。索引5入栈。栈: [ 2, 5 ] i=6 (76°): 76 > 72。弹出5，answer[ 5] = 6-5 = 1。栈顶变2 (75°)，76 > 75。弹出2，answer[ 2] = 6-2 = 4。栈空，索引6入栈。栈: [ 6 ] i=7 (73°): 73 < 76，索引7入栈。栈: [ 6, 7 ] 遍历结束。最终结果: [ 1,1,4,2,1,1,0,0 ]