LeetCode 739. 每日温度

739. 每日温度

解题思路

使用单调栈（单调递减栈）来存储数组下标，栈中的下标对应的温度是递减的（从栈底到栈顶）

• 当前遍历的温度如果大于栈顶温度，说明找到了距离栈顶温度最近的下一个更高温度，此时就可以计算出距离栈顶温度最近的下一个更高温度出现的天数，并将结果存储在结果数组中。
• 如果当前温度不大于栈顶温度，则将当前温度的索引入栈，继续遍历下一个温度，保持栈的单调递减性质。

参考代码

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] res = new int[temperatures.length];
        Stack<Integer> stack = new Stack<>();

        for(int i = 0; i < temperatures.length; i ++) {
            // 若栈不为空,且 今天的温度 大于 栈顶温度，那么就找到了 距离栈顶温度最近的 下一个更高温度: 即今天
            while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int index = stack.peek();
                // 距离栈顶温度最近的下一个更高温度出现在 = [今天-栈顶温度那天的下标] 天后
                res[index] = i - index; 
                stack.pop();
            }
            // 将当前温度的索引入栈
            stack.push(i);
        }
        return res;
    }
}