LeetCode 739 每日温度题解

请根据每日气温列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。
如果气温在这之后都不会升高，请在该位置用 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

单调栈

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n];
        //单调递增栈,放index
        Deque<Integer> upStack = new LinkedList<>();
        //从右往左
        for(int i = n - 1; i >= 0; i--){
            while(!upStack.isEmpty() && temperatures[i] >= temperatures[upStack.getFirst()]){
                upStack.removeFirst();
            }
            if(!upStack.isEmpty()){
                res[i] = upStack.getFirst() - i;//坐标差即为结果
            }else{
                res[i] = 0;
            }
            upStack.addFirst(i);
        }
        return res;
    }
}