https://leetcode.cn/problems/daily-temperatures/description/?envType=study-plan-v2&envId=top-100-liked

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

真暴力会超时

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n];
        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                if(temperatures[j]>temperatures[i]){
                    res[i]=j-i;
                    break;
                }
            }
        }
        return res;
    }
}

这种类型的题用单调栈。一个例子

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