739. Daily Temperatures

739. Daily Temperatures

Difficulty: Medium

Given a list of daily temperatures T, 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, put 0 instead.

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

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

1.Stack

利用栈来消除多余的降序数，例如：1, 3, 5, 7, 4, 3, 8中的4, 3在7之后，所以在后续的遍历中完全无用，通过栈可以跳过这部分数据。

class Solution {
    public int[] dailyTemperatures(int[] T) {
        int r[] = new int[T.length];
        Stack<Integer> stack = new Stack<>();
        
        for (int i = T.length - 1; i >= 0 ; i--) {
            while (!stack.isEmpty() && T[stack.peek()] <= T[i]) {stack.pop();}
            
            if (!stack.isEmpty()) {
                r[i] = stack.peek() - i;
            } 
            stack.push(i);
        }
        return r;
    }
}

时间复杂度O(n)，空间复杂度O(m)

2.DP

由于方法1中对栈的操作相对耗时，还是沿用上述跳过无效数据的思想，可以直接通过结果数组来实现。

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

时间复杂度O(n)，空间复杂度O(1)