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]

示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

输入: temperatures = [30,60,90]
输出: [1,1,0]

提示：

• 1 <= temperatures.length <= 10^5
• 30 <= temperatures[i] <= 100

递减栈-正序遍历

以栈内元素为主。

栈里存递减元素的索引，如果遇到的新元素比栈顶对应的元素大，就弹出栈顶索引，然后计算距离作为栈顶索引对应的答案。然后再比较新元素和栈顶索引对应元素的大小，再执行前面的逻辑。直到栈顶元素大于等于新元素时结束，然后把新元素的索引入栈。

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        // 获取温度数组的长度
        int length = temperatures.length;
        // 创建结果数组，初始化为 0，题目说找不到就取0
        int[] ans = new int[length];
        // 使用 Deque 作为栈，存储温度的索引
        Deque<Integer> stack = new LinkedList<>();
        
        // 遍历温度数组
        for (int i = 0; i < length; i++) {
            // 栈不为空且当前温度大于栈顶索引对应的温度
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                // 弹出栈顶索引。弹出无用元素。
                int prevIndex = stack.pop();
                // 计算当前索引与弹出索引的差值，即等待天数，这是栈顶元素的答案，不是当前元素的答案
                ans[prevIndex] = i - prevIndex;
            }
            
            // 清洗完成后将当前索引压入栈，注意栈里存的是索引
            stack.push(i);
        }
        
        // 返回结果数组
        return ans;
    }
}

时间复杂度O(n)，空间复杂度O(n)。

递减栈-倒序遍历

这个问题本质上也是找下一个更大元素，只不过现在不是问你下一个更大元素的值是多少，而是问你当前元素距离下一个更大元素的索引距离而已。

和正序遍历的区别是倒序遍历计算的是还未入栈的元素的结果，而正序遍历计算的是栈内元素的结果。同时，倒序遍历时栈里存的是后面的索引，因此距离是栈内索引减去当前索引。

class Solution {
    int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n]; // 用于存储结果数组
        // 使用 Deque 作为栈来存储温度的索引
        Deque<Integer> stack = new ArrayDeque<>();

        // 从后往前遍历温度数组
        for (int i = n - 1; i >= 0; i--) {
            // 维护一个单调递减栈，栈中的索引对应的温度由栈底到栈顶递减
            while (!stack.isEmpty() && temperatures[stack.peek()] <= temperatures[i]) {
                stack.pop(); // 弹出栈顶，直到找到一个比当前温度高的温度索引
            }
            // 如果栈为空，说明当前没有找到更高的温度
            // 否则，栈顶元素即为第一个更高的温度索引，计算间距
            res[i] = stack.isEmpty() ? 0 : (stack.peek() - i);
            // 将当前索引入栈
            stack.push(i);
        }
        
        return res; // 返回结果数组
    }
}

分析它的时间复杂度，要从整体来看：总共有 n 个元素，每个元素都被 push 入栈了一次，而最多会被 pop 一次， 没有任何冗余操作。所以总的计算规模是和元素规模 n 成正比的，也就是 O(n) 的复杂度。