Daily Temperatures

stack, monotonous stack

Given a list of daily temperaturesT, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put0instead.

For example, given the list of temperaturesT = [73, 74, 75, 71, 69, 72, 76, 73], your output should be[1, 1, 4, 2, 1, 1, 0, 0].

Note:The length oftemperatureswill be in the range[1, 30000]. Each temperature will be an integer in the range[30, 100].

Analysis

Brute-force

Brute-force的方法就略去不表，时间复杂度O(n^2)。

Stack

Brute-force有很多是重复搜索，更有效率的是利用Stack，一个单调递增的stack。逆序的方式进行扫描。

举例：

T = [73, 74, 75, 71, 69, 72, 76, 73]

如下：

When i = 7, stack = [7 (73)]. ans[i] = 0.
When i = 6, stack = [6 (76)]. ans[i] = 0.
When i = 5, stack = [5 (72), 6 (76)]. ans[i] = 1.
When i = 4, stack = [4 (69), 5 (72), 6 (76)]. ans[i] = 1.
When i = 3, stack = [3 (71), 5 (72), 6 (76)]. ans[i] = 2.
When i = 2, stack = [2 (75), 6 (76)]. ans[i] = 4.
When i = 1, stack = [1 (74), 2 (75), 6 (76)]. ans[i] = 1.
When i = 0, stack = [0 (73), 1 (74), 2 (75), 6 (76)]. ans[i] = 1.

对于结果来说：

ans[i] = stack.isEmpty() ? 0 : stack.peek() - i;

注意：

T[i] >= T[stack.peek()]时候要不断pop()，然后再放入当前下标i。这里要允许"="的条件，因为需要寻找第一个出现的位置，因此重复位置要pop()出来。

这一题用Stack很妙，十分经典。As @FrancisGee points out:

When I saw the question in this competition, I firstly think about Monotonous stack inspired by Largest Rectangle in Histogram. Because Monotonous stack can help us find first largest element in O(n) time complexity.

这种单调栈的思想需要多加琢磨咀嚼。

Time Complexity - O(n)

Space Complexity - O(n)

Solution

Stack with reverse order iteration T.length - 1 to 0 - Time: O(n), Space: O(n) - (52 ms)

class Solution {
    public int[] dailyTemperatures(int[] T) {
        int[] ans = new int[T.length];
        Deque<Integer> stack = new ArrayDeque<>();    

        for (int i = T.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && T[i] >= T[stack.peek()]) {
                stack.pop();
            }
            ans[i] = stack.isEmpty() ? 0 : stack.peek() - i;
            stack.push(i);
        }
        return ans;
    }
}

Stack with 0 to T.length - 1 order iteration (17 ms, faster than 92.98%)

Using ArrayDeque() will significantly increase performance than Stack()

class Solution {
    public int[] dailyTemperatures(int[] T) {
        Deque <Integer> stack = new ArrayDeque<>();
        int[] ret = new int[T.length];
        for (int i = 0; i < T.length; i++) {
            while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
                int idx = stack.pop();
                ret[idx] = i - idx;
            }
            stack.push(i);
        }
        return ret;
    }
}

Brute-force O(n^2) - (348 ms)

class Solution {
    public int[] dailyTemperatures(int[] T) {
        int n = T.length;
        int[] ans = new int[n];
        int days = 0;
        for (int i = 0; i < n; i++) {
            days = 0;
            for (int j = i; j < n; j++) {
                if (T[j] > T[i]) {
                    ans[i] = days;
                    break;
                } else {
                    days++;
                }
            }
        }
        return ans;
    }
}