算尽天下|算法|题解

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

jxtxzzw · 2月13日 · 2020年 · · · 275次已读

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

    }
}

共 2 条评论
说点什么

avatar

您可以根据需要插入表情、图片、音频、视频或者其他附件,也可以 @ 你需要提及的用户

  
不开心么么什么再见加油发火可以可怜可爱吐吐血吓呵呵哈哈哦哭哼喜欢嗯嘿嘿困圣诞坏笑圣诞调皮坏笑女汉子奸笑好的委屈宝宝害羞小清新心塞快哭了恭喜发财惆怅我最美抓狂抠鼻放空无奈晕汗泪奔温柔女生狗年生气笑笑泪衰调皮调皮女生鄙视酷静静额鼓掌
上传图片
 
 
 
上传视频和音频
 
 
 
上传其他类型文件
 
 
 
1 评论主题数
1 评论回复数
0 评论跟进人数
 
最近回复的评论
最热烈的讨论
2 评论人数
jxtxzzwRobin 最近评论者

  订阅评论动态  
最新 最旧 得票最多
提醒
    Robin
    Robin3 月 之前 [2020-2-15 · 9:39]
    Chrome 80.0.3987.87 Windows 10

    好题,感谢分享,补充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,找到最小的下标差(二分找),能过
    虽然时间复杂度比较高,但有时候想不到比较好的方法的时候去钻一些数据的空子做暴力也不失为一个办法