739 每日温度

一、题目

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

二、题解

思路：单调栈

单调栈专门用于解决 “寻找下一个更大（或更小）元素” 的问题。

• 原理：我们维持一个栈，里面存放温度的下标。
• 操作：遍历数组，如果当前气温比“栈顶下标对应的气温”高，说明我们找到了栈顶元素“下一个更高”的一天。
• 效果：每个元素只进栈一次、出栈一次，时间复杂度直接降到 $O(n)$。

import java.util.Deque;
import java.util.LinkedList;

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n];
        // 栈里存的是下标
        Deque<Integer> stack = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            // 如果当前温度大于栈顶下标对应的温度
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int prevIndex = stack.pop(); // 弹出栈顶
                res[prevIndex] = i - prevIndex; // 计算间距
            }
            // 将当前下标入栈
            stack.push(i);
        }

        return res;
    }
}

时间复杂度：$O(N)$

空间复杂度：$O(n)$