LeetCode 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

样例

样例输入

73 74 75 71 69 72 76 73

样例输出

1 1 4 2 1 1 0 0

算法与数据结构

栈

题解

一种显然的解法是对于每一天，遍历这一天之后所有的数据：

for (int i = 0; i < temperature.length; i++) {
    for (int j = i + 1; j < temperature.length; j++) {
        if (temperature[j] > temperature[i]) {
            ans[i] = j - i;
            break;
        }
    }
}

但是这样的时间复杂度是 $O(n^2)$。
考虑下面这种情况：20 19 18 21。
首先看 20℃ 下一天，遇到 19℃，继续，遇到 18℃，继续，遇到 21℃，中间经过了 3 天。
接着来看 19℃，遇到 18℃，继续，遇到 21℃，中间经过了 2 天。
等等，“遇到 18℃，继续，遇到 21℃”这句话，是不是似曾相识？在查找 20℃ 的时候，我明明已经知道了 19℃ 的下一天是 18℃ 啊，我已经知道了接下来遇到 21℃ 才是我要的答案，我为什么要一遍又一遍地重复这件事情？
下面将使用栈这种数据结构将该算法优化成 $O(n)$。
由于只需要计算中间间隔的天数，所以我们只需要把数组的下标压入栈，然后用 temperature[stack.top()] 进行比较就可以了。但是为了讲解方便，下面将同时给出对应的温度。
temperature[] = {73, 74, 75, 71, 69, 72, 76, 73}

• 初始栈为 []；
• 对第 index = 0 个温度 73，栈为空，把它的下标 0 压入堆栈；栈为 [0]（[73℃]），栈顶元素 stack.top() = 0，对应 temperature[stack.top()] = 73；
• 下一个温度 index = 1, temperature[index] = 74，高于 temperature[stack.top()] = 73，因此 73 温度升高只需 1 - 0 = 1 天时间，把 73 度下标 0 从栈里弹出，把 74 度下标 1 压入；栈为 [1]（[74℃]），栈顶元素 stack.top() = 1，对应 temperature[stack.top()] = 74；
• 同样，从 74 度只需要 1 天时间升高到 75 度；栈为 [2]（[75℃]），栈顶元素 stack.top() = 2，对应 temperature[stack.top()] = 75；
• index = 3, temperature[index] = 71 度，低于 temperature[stack.top()] = 75 度，直接把 71 度下标 3 压入堆栈；栈为 [2, 3]（[75℃, 71℃]），栈顶元素 stack.top() = 3，对应 temperature[stack.top()] = 71；
• 69 度低于 71 度，压入堆栈；栈为 [2, 3, 4]（[75℃, 71℃, 69℃]），栈顶元素 stack.top() = 4，对应 temperature[stack.top()] = 69；
• index = 5, temperature[index] = 72 度高于 temperature[stack.top()] = 69 度，从 69 度升温只需 5 - 4 = 1 天，此时将栈顶元素出栈，栈为 [2, 3]（[75℃, 71℃]），栈顶元素 stack.top() = 3，对应 temperature[stack.top()] = 71，依然小于 72 度，于是从 71 度升温需要 5 - 3 = 2 天，并继续出栈栈顶元素，栈为 [2]（[75℃]），72 度低于 75 度，意味着尚未找到 75 度之后的升温，直接把 72 度下标 5 压入堆栈顶端，栈为 [2, 5]（[75℃, 72℃]）；
• 后面的温度与此同理……
  该方法只需要对数组进行一次遍历，每个元素最多被压入和弹出堆栈一次，算法复杂度是 $O(n)$。

核心代码详述

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

完整代码

import java.util.Stack;

public class LeetCode {

    public static void main(String[] args) {
        int[] temperature = {73, 74, 75, 71, 69, 72, 76, 73};
        int[] ans = new int[temperature.length];
        Stack<Integer> s = new Stack<>();
        for (int i = temperature.length - 1; i >= 0; i--) {
            while (!s.isEmpty() && temperature[s.peek()] <= temperature[i]) {
                s.pop();
            }
            ans[i] = s.isEmpty() ? 0 : s.peek() - i;
            s.push(i);
        }
        for (int x: ans) {
            System.out.print(x + " ");
        }

    }
}