力扣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]

思路

1. 暴力for、for
2. 单调栈
   维护一个有序的栈，当第i个数据比栈顶数据大时，一直弹出栈顶元素，更新下标差（所以，栈存的是下表）；将第i个元素入栈。

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int len = temperatures.length;
        int next[] = new int[len];
        Stack<Integer> stk = new Stack<Integer>();
        for (int i=0; i<len; i++){
            while(!stk.empty() && temperatures[i]>temperatures[stk.peek()]){
                int idx = stk.pop();
                next[idx] = i-idx;
            }
            stk.push(i);
        }
        return next;
    }
}