[LC]739. 每日温度

🚩传送门：力扣题目

题目

给定一个整数数组 ，表示每天的温度，返回一个数组 ，其中 是指在第 天之后，才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 来代替。

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0]

解题思路：单调栈

可以维护一个存储下标的单调栈，从栈底到栈顶的下标对应的温度列表中的温度依次递减。如果一个下标在单调栈里，则表示尚未找到下一次温度更高的下标。
正向遍历温度列表。对于温度列表中的每个元素

• 如果栈为空，则直接将 进栈
• 如果栈不为空，则比较栈顶元素 对应的温度 和当前温度 。

1. 如果 ，则直接将 进栈。
2. 否则将 移除，并将 对应的等待天数赋为

流程：

• 当 时，单调栈为空，因此将 进栈。

  

• 当 时，由于 ，因此移除栈顶元素 ，赋值 ，将 进栈。

  

• 当 时，由于 ，因此移除栈顶元素 ，赋值 ，将 进栈。

  

• 当 时，由于 ，因此将 进栈。

  

• 当 时，由于 ，因此将 进栈。

  

• 当 时，由于 ，因此依次移除栈顶元素 和 ，赋值 ，将 进栈。

  

• 当 时，由于 ，因此依次移除栈顶元素 和 ，赋值 ，将 进栈。

  

• 当 时，由于，因此将 进栈。

  

复杂度分析

时间复杂度：，其中 是温度列表的长度。正向遍历温度列表一遍，对于温度列表中的每个下标，最多有一次进栈和出栈的操作。

空间复杂度：，其中 是温度列表的长度。需要维护一个单调栈存储温度列表中的下标。

我的代码

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int length = temperatures.length;
        int[] ans = new int[length];
        LinkedList<Integer> stack = new LinkedList<Integer>();
        for (int i = 0; i < length; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int top = stack.pop();
                ans[top] = i - top;
            }
            stack.push(i);
        }
        return ans;
    }
}