739. 每日温度

中等

题目描述

解法：单调栈
遍历 temperatures 数组并维护一个单调栈，栈存放元素在 temperatures 中的位置

• 如果栈为空，将元素入栈
• 如果遍历到的元素比栈底小，则入栈
• 如果遍历到的元素比栈底大，则找到了更大的温度。执行出栈操作，并计算位置差。

public int[] dailyTemperatures(int[] temperatures) {
    int[] res = new int[temperatures.length];
    Deque<Integer> deque = new LinkedList<>();
    for (int i = 0; i < temperatures.length; i++) {
        int temperature = temperatures[i];
        while (!deque.isEmpty() && temperature > temperatures[deque.peek()]) {
            int prevIndex = deque.pop();
            res[prevIndex] = i - prevIndex;
        }
        deque.push(i);
    }
    return res;
}