LeetCode 739. 每日温度

class Solution {
    public int[] dailyTemperatures(int[] T) {
        // int[] results = new int[T.length];
        // for (int i = 0; i < T.length; i++) {
        //     int wait = 0;
        //     for (int j = i + 1; j < T.length; j++) {
        //         if (T[j] > T[i]) {
        //             wait = j - i;
        //             break;
        //         }
        //     }
        //     results[i] = wait;
        // }
        // return results;

        // 单调栈
        int[] results = new int[T.length];
        Deque<Integer> stack = new LinkedList<Integer>();
        for (int i = 0; i < T.length; i++) {
            while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
                int pre = stack.pop();
                results[pre] = i - pre;
            }
            stack.push(i);
        }
        return results;
    }
}