739-每日温度

leetcode 链接：https://leetcode-cn.com/problems/daily-temperatures/

解法

可以维护一个存储下标的单调栈，从栈底到栈顶的下标对应的温度列表中的温度依次递减。如果一个下标在单调栈里，则表示尚未找到下一次温度更高的下标。

正向遍历温度列表。对于温度列表中的每个元素 T[i]，如果栈为空，则直接将 i 进栈，如果栈不为空，则比较栈顶元素 prevIndex 对应的温度 T[prevIndex] 和当前温度 T[i]，如果 T[i] > T[prevIndex]，则将 prevIndex 移除，并将 prevIndex 对应的等待天数赋为 i - prevIndex，重复上述操作直到栈为空或者栈顶元素对应的温度小于等于当前温度，然后将 i 进栈。

为什么可以在弹栈的时候更新 ans[prevIndex] 呢？因为在这种情况下，即将进栈的 i 对应的 T[i] 一定是 T[prevIndex] 右边第一个比它大的元素，试想如果 prevIndex 和 i 有比它大的元素，假设下标为 j，那么 prevIndex 一定会在下标 j 的那一轮被弹掉。

由于单调栈满足从栈底到栈顶元素对应的温度递减，因此每次有元素进栈时，会将温度更低的元素全部移除，并更新出栈元素对应的等待天数，这样可以确保等待天数一定是最小的

class Solution {
    public int[] dailyTemperatures(int[] T) {
        int len = T.length;
        // 创建数组栈：数组中存放原数组下标
        int[] stack = new int[len];
        // 栈指针
        int pos = -1;
        // 结果数组
        int[] res = new int[len];
        // 一次遍历
        for (int i = 0; i < len; i++) {
            while (pos >= 0 && T[stack[pos]] < T[i]) {
                res[stack[pos]] = i - stack[pos--];
            }
            stack[++pos] = i;
        } 
        // 遍历栈
        while (pos >= 0) {
            res[stack[pos--]] = 0;
        }
        return res;
    }
}