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]

思路

暴力做法是对每一天往后找第一个更高气温，O(n²)。更优的是单调栈：栈里维护”还没找到更高气温的日子的下标”，保持栈内下标对应的温度是递减的。

遍历到第 i 天时，只要栈顶温度比今天低，就说明栈顶那天等到了更高气温，弹出并计算 i - 栈顶下标 就是它等待的天数；重复弹出直到栈顶温度不低于今天，再把 i 压栈。这样每个下标最多入栈出栈各一次。

代码

public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] result = new int[n];
    Deque<Integer> stack = new ArrayDeque<>(); // 存下标，对应温度递减
 
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int prevIndex = stack.pop();
            result[prevIndex] = i - prevIndex;
        }
        stack.push(i);
    }
    return result;
}

复杂度

• 时间：O(n) — 每个下标入栈、出栈各一次，均摊 O(1)
• 空间：O(n) — 最坏情况（温度递减）栈存满所有下标

边界条件

• 温度单调递减（如 [73,72,71]）：每天都直接压栈，从不触发弹出，最终所有 result[i] 保持初始值 0（因为 int[] 默认初始化为 0，代表”之后都没有更高气温”）。
• 温度单调递增（如 [71,72,73]）：每天都会让栈顶弹出，result 每一位都是 1。
• 只有一天：栈中压入唯一下标，循环结束，result[0] 保持默认值 0。

变式

• 单调栈是一类模板题的核心：找”下一个更大/更小元素”都是同一套思路，84. 柱状图中最大矩形 是它的进阶应用。
• 求”下一个更大元素”是循环数组（首尾相连）：可以把数组长度视为 2n，遍历时对下标取模 i % n，其余逻辑不变。

易错点

• 栈里存的是下标而不是温度值，因为最终要计算的是”等待的天数”（下标差），如果只存温度值就无法算出距离。
• while 循环条件是”栈非空且当前温度大于栈顶对应的温度”，不能写成 if——一天可能同时让多个更低的历史天数结算（比如温度突然大幅上升），必须用循环弹出所有满足条件的下标。

面试追问

• 为什么维护的是”递减”栈，而不是”递增”栈？ 因为我们要找的是”下一个比当前更高的温度”，递减栈保证了栈里的下标对应的温度是从栈底到栈顶递减的，一旦新温度比栈顶高，说明栈顶那天等到了它的答案；如果维护递增栈就无法用这种”新元素一来就能触发结算”的方式工作。
• 暴力解法是 O(n²)，单调栈为什么能优化到 O(n)？能证明均摊复杂度吗？ 暴力解法对每天都要往后扫描找第一个更高温度，单调栈让每个下标只入栈一次、出栈一次（一旦出栈就不会再入栈），所以总的入栈出栈次数是 O(n)，均摊到每一天是 O(1)，整体是 O(n)。

关联题

• 同套路：496. 下一个更大元素 I、503. 下一个更大元素 II（循环数组：下标取模跑两圈）—— 单调栈找”下一个更大”全家桶
• 进阶：84. 柱状图中最大矩形 —— 从”下一个更大”升级为”两侧第一个更小”
• 知识点：单调栈专题见单调栈与单调队列；O(n) 的证明是摊还——每个下标入栈出栈各一次，内层 while 的总弹出次数被总入栈次数锁死