单调栈：每日温度

题目

给定一个整数数组 temperatures​ ，表示每天的温度，返回一个数组 answer​ ，其中 answer[i]​ 是指对于第 i​ 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0​ 来代替。

示例1：

输入：temperatures = [30, 40, 50, 60]

输出：[1, 1, 1, 0]

示例2：

输入：temperatures=[30, 60, 90]

输出：[1, 1, 0]

解答

Java

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int length = temperatures.length;
        int[] ans = new int[length];
        Deque<Integer> stack = new LinkedList<Integer>();
        for (int i = 0; i < length; i++) {
            int temperature = temperatures[i];
            // 当前元素大于栈顶元素，则不断的从栈中移出元素，直到栈中元素不再小于当前元素
            // 栈，从栈底到栈顶元素是减小的，因为较小的元素在每次比对的时候都被移除了
            // 栈中的元素代表着待处理的元素
            while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) {
                int prevIndex = stack.pop();
                // 当前元素的索引和栈顶元素的索引的差值便是期望的结果
                ans[prevIndex] = i - prevIndex;
            }
            // 将当前元素入栈，维护栈仍然为一个递减单调栈
            // 每个元素至少会入栈一次
            stack.push(i);
        }
        return ans;
    }
}