739. 每日温度

根据每日 气温 列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/daily-temperatures 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目解析：

给定列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，为啥输出就是 [1, 1, 4, 2, 1, 1, 0, 0] ？

下面来一个个进行解释。

  • 对于输入 73，它需要 经过一天 才能等到温度的升高，也就是在第二天的时候，温度升高到 74 ，所以对应的结果是 1。
  • 对于输入 74，它需要 经过一天 才能等到温度的升高，也就是在第三天的时候，温度升高到 75 ，所以对应的结果是 1。
  • 对于输入 75，它经过 1 天后发现温度是 71，没有超过它，继续等，一直 等了四天，在第七天才等到温度的升高，温度升高到 76 ，所以对应的结果是 4 。
  • 对于输入 71，它经过 1 天后发现温度是 69，没有超过它，继续等，一直 等了两天，在第六天才等到温度的升高，温度升高到 72 ，所以对应的结果是 2。
  • 对于输入 69，它 经过一天 后发现温度是 72，已经超过它，所以对应的结果是 1 。
  • 对于输入 72，它 经过一天 后发现温度是 76，已经超过它，所以对应的结果是 1 。
  • 对于输入 76，后续 没有温度 可以超过它，所以对应的结果是 0 。对于输入 73，后续 没有温度 可以超过它，所以对应的结果是 0 。

题解：

理解了题目，我们开始解题

思路一：暴力法

  • 从头到位遍历元素，取到当前元素与其后边元素挨个比较
    • 当后边元素 <= 当前元素时，继续向后遍历
    • 当 后边元素 > 当前元素时，当前元素升高需要 j - i天 (j , i分别代表后边元素 和 当前元素的下标)
    • 遍历到最后，一只没有比当前元素大的温度，则其为0

代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

public int[] dailyTemperatures(int[] T) {
    int[] res = new int[T.length];
    for (int i = 0; i < T.length - 1; i++) {
        int n1 = T[i];
        for (int j = 0; j < T.length; j++) {
            if (T[j] > n1){
                res[i] = j - j;
                break;
            }
        }
    }
    return res;
}

复杂度分析

时间复杂度 : O(N ^ 2)

空间复杂度 : O(1)

提交后， 虽然ac了，但是耗时很长，见截图。

屏幕快照 2020-06-11 下午1.21.31

思路二： 单调递减栈

题目的标签是栈，那么我们是否可以利用栈来解决问题呢？答案是可以的，利用单调递减栈

  • 初始化一个栈，并且维护此栈的元素从栈底到栈顶单调递减，栈中存放元素的下标

  • 从头到尾遍历元素

    • while循环执行条件： 栈为空 并且 元素 大于 栈顶元素 时
      • res[stack.peek()] = i - stack.pop();
    • while执行完毕，则一定满足 栈为空，或者元素小于等于栈顶元素时
      • 这时，将元素的下标直接入栈

下边我在纸上模拟了一遍，第一个测试用例 使用单调递减栈 的执行流程，如图:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

public int[] dailyTemperatures(int[] T) {
    int[] res = new int[T.length];
    // 单调递减栈, 存放元素下标
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < T.length; i++) {
        // 栈不为空 且 当前元素 > 栈顶元素
        while (!stack.isEmpty() && T[stack.peek()] < T[i]){
            res[stack.peek()] = i - stack.pop();
        }
        
        // while循环执行完毕，一定满足 两个条件:栈为空 或者 当前元素 <= 栈顶元素 两者之一
        // 直接把当前元素的 下标 入栈
        stack.push(i);
    }
    return res;
}

复杂度分析 :

时间复杂度 : O(N)

空间复杂度 : O(N)

此解法，就比暴力法 优秀很多了.

屏幕快照 2020-06-11 下午1.40.28

思路三：从后往前 动态规划

  • 根据题意，从最后一天推到第一天，会简单很多。第一天显然没有升高的可能，结果为0.
  • 再看倒数第二天，如果比倒数第一天低， 则为1。如果比倒数第一天高，则也为0
  • 由此可见。 求第 i 天的天数时
    • 如果 T[i + 1] > T[i], 则 res[i] = 1
    • 如果 T[i + 1] < T[i]
      • 如果 res[i + 1] == 0, 则表明 i + 1 以后不会再升高。 所以 res[i] = 0
      • 如果 res[i + 1] != 0, 那么就比较 T[i] 和 T[i + i + res[i + 1]] (也就是比较 第 i 天的温度 和 比 i+1 天 温度高的那天的温度)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

/**
     * 
     * - 根据题意，从最后一天推到第一天，会简单很多。第一天显然没有升高的可能，结果为0.
     * - 再看倒数第二天，如果比倒数第一天低， 则为1。如果比倒数第一天高，则也为0
     * - 由此可见。 求第 i 天的天数时
     *   - 如果 T[i + 1] > T[i], 则 res[i] = 1
     *   - 如果 T[i + 1] < T[i]
     *     - 如果 res[i + 1] == 0, 则表明 i + 1 以后不会再升高。 所以 res[i] = 0
     *     - 如果 res[i + 1] != 0, 那么就比较 T[i] 和 T[i + i + res[i + 1]] (也就是比较 第 i 天的温度 和 比 i+1 天 温度高的那天的温度)
     * 
     * */
    public int[] dailyTemperatures1(int[] T) {
        // 存放结果的数组
        int[] dp = new int[T.length];
        
        // 倒是第一天，肯定不会升高， 为0。 
        // 可以省略这句，因为int[] 在 java中每个元素初始值就是 0
        dp[T.length - 1] = 0;

        // 从倒数第二天开始计算升高的天数
        for (int i = T.length - 2; i >= 0; i--) {
            int j = i + 1;
            while (j < T.length){
                // 如果 i + 1天 > i天。 则res[i] 为 i
                if (T[j] > T[i]){
                    dp[i] = j - i;
                    break;
                }else if (dp[j] == 0){
                    // 如果 i + 1天 <= i天。
                    // 并且 res[i + 1] == 0， 说明i + 1以后不会升高。 所以 res[i] = 0
                    dp[i] = 0;
                    break;
                }else {
                    // 否则，while循环继续比较 i + 1 + res[i + 1] 位置 和 i位置的大小 
                    j += dp[j];
                }
            }
        }
        return dp;
    }

屏幕快照 2020-06-11 下午2.01.43