739. 每日温度

📝 题目描述

给定一个整数数组 temperatures，表示每天的温度，返回一个数组 answer，其中 answer[i] 是对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

---

📌 示例

示例 1

输入：

temperatures = [73,74,75,71,69,72,76,73]

输出：

[1,1,4,2,1,1,0,0]

解释：

• 第0天（73）的下一个更高温度是第1天（74），差1天；
• 第2天（75）的下一个更高温度是第6天（76），差4天；
• 第6天（76）之后无更高温度，记为0。

示例 2

输入：

temperatures = [30,40,50,60]

输出：

[1,1,1,0]

示例 3

输入：

temperatures = [30,60,90]

输出：

[1,1,0]

---

🚀 最优解：单调栈（维护递减下标序列）

🔍 思路解析

核心贪心策略：用单调栈维护“未找到更高温度的天数下标”，栈内下标对应的温度呈递减顺序；遍历数组时，若当前温度高于栈顶下标对应的温度，就计算天数差并弹出栈顶，直到栈空或当前温度不更高，再将当前下标入栈。

1. 初始化：
   • stack：存储温度数组的下标，保持栈内下标对应的温度递减；
   • ans：结果数组，初始值全为0；
2. 遍历温度数组的每个下标 i：
   • 循环判断：若栈非空，且当前温度 temperatures[i] > temperatures[stack.peek()]（当前温度更高）：
     • 弹出栈顶下标 pre（代表之前的某一天）；
     • 计算天数差：ans[pre] = i - pre；
   • 将当前下标 i 入栈（等待后续更高温度）；
3. 遍历结束后，ans 即为结果（未弹出的下标对应 ans 为0）。

---

✅ 完整代码（Java）

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Read temperatures array
        String input = scanner.nextLine();
        input = input.substring(1, input.length() - 1); // Remove brackets
        String[] temps = input.split(",");

        int[] temperatures = new int[temps.length];
        for (int i = 0; i < temps.length; i++) {
            temperatures[i] = Integer.parseInt(temps[i].trim());
        }

        Solution solution = new Solution();
        int[] result = solution.dailyTemperatures(temperatures);

        // Print result array
        System.out.print("[");
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i]);
            if (i < result.length - 1) {
                System.out.print(",");
            }
        }
        System.out.println("]");

        scanner.close();
    }
}

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        Stack<Integer> stack = new Stack<>(); // 存储下标，保持温度递减
        int[] ans = new int[n]; // 结果数组，默认全0

        for (int i = 0; i < n; i++) {
            // 当前温度 > 栈顶下标对应的温度 → 计算天数差
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int pre = stack.pop(); // 弹出之前的天数下标
                ans[pre] = i - pre;    // 记录天数差
            }
            stack.add(i); // 当前下标入栈，等待后续更高温度
        }
        return ans;
    }
}

---

🧠 通俗易懂解释

可以把栈想象成“等待‘升温’的排队队伍”：

• 每个“队员”是某一天的下标，队伍里的队员对应的温度是“越来越低”的（后面的队员比前面的冷）；
• 新来了一个“队员i”（当前天），如果他比队首的队员更热，就把队首的队员“放出去”，并告诉队首队员：“你等了i - 队首下标天，我就是你要等的更高温度”；
• 重复这个过程，直到队首队员比“队员i”冷，或者队伍空了，“队员i”再加入队伍等待自己的更高温度。

以示例1 temperatures = [73,74,75,71,69,72,76,73] 为例：

1. i=0（73）：栈空，入栈 → 栈：[0]；
2. i=1（74）：74>73（栈顶0的温度），弹出0 → ans[0]=1-0=1，入栈1 → 栈：[1]；
3. i=2（75）：75>74（栈顶1的温度），弹出1 → ans[1]=2-1=1，入栈2 → 栈：[2]；
4. i=3（71）：71<75，入栈3 → 栈：[2,3]；
5. i=4（69）：69<71，入栈4 → 栈：[2,3,4]；
6. i=5（72）：72>69（栈顶4）→ 弹出4，ans[4]=5-4=1；72>71（栈顶3）→ 弹出3，ans[3]=5-3=2；72<75（栈顶2），入栈5 → 栈：[2,5]；
7. 后续步骤以此类推，最终得到结果数组。

---

⏱ 时间复杂度

O(n)

每个下标仅入栈、出栈各一次，遍历数组的时间为线性级。

---

💾 空间复杂度

O(n)

栈的最大空间为 n（最坏情况温度数组严格递减，所有下标都入栈）。

---