[LeetCode Hot 100] LeetCode739. 每日温度

题目描述

思路：单调递减栈

使用单调栈的模板即可。
根据题意可知，该题使用的是单调递减栈。
问题抽象为：找出数组中右边第一个比我大的元素。

方法一：

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        // 用于存放结果
        int[] res = new int[temperatures.length];
        // 单调递减栈，栈中存放的是索引
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < temperatures.length; i ++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                res[stack.peek()] = i - stack.peek();
                stack.pop();
            }
            stack.push(i);
        }
        return res;
    }
}

时间复杂度：O(n)
空间复杂度：O(n)