739. 每日温度

这是经典的 单调栈（Monotonic Stack） 问题。我们可以用一个栈来维护尚未找到更高温度的日期索引。

🧠 思路：

• 遍历 temperatures 数组。
• 使用一个栈，栈中保存的是 天数的索引，且对应的温度是 递减的。
• 对于当前天 i：
  • 如果当前温度比栈顶索引对应的温度高，说明找到了「下一个更高温度」。
  • 不断弹出栈顶，直到栈为空或当前温度不大于栈顶温度。
  • 每次弹出时，计算天数差 i - index，填入 answer[index]。
• 最后将当前索引 i 入栈。

✅ Java 代码实现：

import java.util.*;

public class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = 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();
                answer[prevIndex] = i - prevIndex;
            }
            stack.push(i);
        }

        // 栈中剩下的元素默认 answer 为 0（Java 数组初始化就是 0）
        return answer;
    }
}

📌 示例：

输入：

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、7 天之后没有更高温度，所以为 0。

⏱️ 时间复杂度：

• O(n)：每个元素最多入栈和出栈一次。

🧺 空间复杂度：

• O(n)：栈最多存 n 个索引。