本文写于 2020年02月13日,距今已超过 1 年,距 2020年03月26日 的最后一次修改也已超过 3 个月,部分内容可能已经过时,您可以按需阅读。如果图片无法显示或者下载链接失效,请给我反馈,谢谢!


0 0 投票数
评分

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 投票数
评分
2条留言
订阅评论
提醒
guest

在点击发表评论按钮时,网络请求的数据包含浏览器版本、操作系统版本和 IP 地址;您的网络服务提供商、雇主或学校、政府机构可能会看到您的访问活动;根据浏览器默认行为、操作系统设置和安全防护软件的设置不同,您的浏览器可能会也可能不会在本地 Cookies 缓存您输入的用户名、邮箱以便下次评论使用。

请对自己的言行负责。

您想以什么身份发表评论
邮箱将在您的评论被回复时给您通知
(可选)如果您也有个人网站,不妨分享一下
我对这篇文章的评分
这篇文章给您带来多大帮助
2 评论
内联反馈
查看所有评论
Robin
Robin (@guest_1923) Chrome 80.0.3987.87 Windows 10
游客
2020年2月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,找到最小的下标差(二分找),能过
虽然时间复杂度比较高,但有时候想不到比较好的方法的时候去钻一些数据的空子做暴力也不失为一个办法