算法

(单调栈) $O(n)$

这题的本质就是在一个一维数组中去求每个元素的右侧第一个比他大的元素，所以是经典的单调栈模版题。我们需要维护一个单调递减的单调栈，这个单调栈中存放的是所有暂时还没有找到结果的元素的下标。这个单调栈的实现逻辑是每遇到一个新的元素的时候，我们都把它跟栈顶的元素进行比较，如果当前栈顶的值比新元素的值要小，那么表示栈顶元素找到了结果，于是就把栈顶元素的结果更新，然后把栈顶元素弹出。

Java 代码

class Solution {
    public int[] dailyTemperatures(int[] T) {
        // 单调递减的单调栈：index to be resolved
        int n = T.length;
        int[] res = new int[n];
        Deque<Integer> stack = new ArrayDeque();
        for (int i = 0; i < n; ++i) {
            while (!stack.isEmpty() && T[stack.getLast()] < T[i]) {
                res[stack.getLast()] = i - stack.getLast();
                stack.removeLast();
            } 
            stack.addLast(i);
        }
        return res;
    }
}