算法|题解

[算尽天下系列第1期]LeetCode·739·每日温度

凝神长老 · 2月13日 · 2020年 · · · 482次已读

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 + " ");
        }

    }
}

0 0 投票
Article Rating
订阅评论动态
提醒
guest
2 评论
最新
最旧 得票最多
行内反馈
查看所有评论
Robin
Robin Chrome 80.0.3987.87 Windows 10
2020-02-15 09:39

好题,感谢分享,补充c++代码

vector dailyTemperatures(vector& T) {
    int n = T.size();
    stack index;
    vector ans(n, 0);
    for(int i=0; i < n; i++){
        while(!index.empty()){
            int idx = index.top();
            if(T[idx] < T[i]){
                ans[idx] = i - idx;
                index.pop();
            }
            else break;
        }
        index.push(i);
    }
    return ans;
}

还有一个很暴力但是能过的想法,利用温度范围为[30, 100]去钻空子,维护一个map,键为温度,值为该温度的下标列表,然后对于每一个温度值T,在[T+1, 100]区间去遍历map,找到最小的下标差(二分找),能过
虽然时间复杂度比较高,但有时候想不到比较好的方法的时候去钻一些数据的空子做暴力也不失为一个办法