739. 每日温度

知识点：栈；单调

题目描述

请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例

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

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

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

---

解法一：单调

这个题目是很典型的单调栈的题，我们可以维持一个单调递减的栈，也就是栈底是最大的，这样，当来一个新元素的时候判断当前元素和栈顶的大小关系，如果当前元素<栈顶，满足递减栈，可以入栈了；如果当前元素>栈顶，那就证明找到了栈顶对应的下一个更大的，然后再看新的栈顶看还大不大了，如果大了那证明也还是新的栈顶的对应的温度。

注意我们在这个单调栈里存的是下标，因为最后要返回的是下标，但是这个下标入栈是根据其对应的值来进入的。

单调栈在解决这种更大，更小类问题时很常用。

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int index = 0;
        int[] res = new int[temperatures.length];
        Stack<Integer> stack = new Stack<>(); //维持一个单调递减的栈；
        while(index < temperatures.length){
            while(!stack.isEmpty() && temperatures[index] > temperatures[stack.peek()]){
                res[stack.peek()] = index-stack.peek();  //存的是下标；
                stack.pop();
            }
            stack.push(index);
            index++;
        }
        return res;
    }
}