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 <= 105
• 30 <= temperatures[i] <= 100

思路：从后往前遍历，维护一个单调栈，更新ans时就能保证栈内的气温比当前值大且是最接近的

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n=temperatures.length-1;
        int[] ans=new int[temperatures.length];
        Deque<Integer> stack = new ArrayDeque<>();
        ans[n]=0;
        stack.push(n);
        n--;
        while(n>=0){
            //如果当前气温比栈内气温高，则弹出
            while(!stack.isEmpty()&&temperatures[stack.peek()]<=temperatures[n]){
                stack.pop();
            }
            //如果栈为空了，说明没有气温比今天高
            if(stack.isEmpty()){
                ans[n]=0;
                stack.push(n);
            }
            //找到下一次高的气温
            else{
                ans[n]=stack.peek()-n;
                stack.push(n);
            }
            n--;
        }
        return ans;
    }
}