72.每日温度

LCR 038. 每日温度

请根据每日 气温 列表 temperatures ，重新生成一个列表，要求其对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1：

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

最优解法：单调栈（时间复杂度 O(n)）

单调栈的核心思想是用栈记录还没找到 “下一个更高温度” 的下标，遍历数组时 “回头” 计算这些下标的等待天数，每个元素只会入栈和出栈一次，总操作次数是 O(n)，能轻松处理大规模输入。【通俗说法：爱幼不尊老，新来的元素比栈顶小入栈；新来的大，吃掉里面比它小的】

这样能保证：小的在栈里的元素能通过 大元素id-小元素id 拿到最终结果ans；大元素因为ans初始化为0 也不用单独再初始化

class Solution {public int[] dailyTemperatures(int[] temperatures) {int n = temperatures.length;int[] ans = new int[n]; // 结果数组，默认值为0// 单调栈：存储温度数组的下标，栈内下标对应的温度单调递减Deque<Integer> stack = new ArrayDeque<>();for (int i = 0; i < n; i++) {// 当前温度 > 栈顶下标对应的温度 → 找到栈顶位置的等待天数while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {int prevIndex = stack.pop(); // 弹出栈顶下标（已找到更高温度）ans[prevIndex] = i - prevIndex; // 计算等待天数
            }// 当前下标入栈（等待后续找到更高温度）
            stack.push(i);}return ans;}
}

【记 思路】

关键思路：单调栈是解决 “下一个更大元素” 类问题的经典方法，核心是 “延迟计算”—— 先记录需要处理的下标，遍历到符合条件的元素时再回头计算结果。