力扣739——每日温度

区块链游侠
• 阅读 1884

这道题主要是找规律,优化的时候可以利用数据结构的特性(数组和栈)。
<!-- more -->

原题

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

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

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

原题url:https://leetcode-cn.com/probl...

解题

优先队列

如果正向思考的话,就是从前向后遍历,将温度存储在一个优先级队列中(小顶堆),队列中的结构需要记录温度和天数。

遍历时需要找到队列中最小的值是否大于当前温度,如果大于,则更新结果;如果小于,则将当前记录放入队列中。

接下来看看代码:

class Solution {
    public int[] dailyTemperatures(int[] T) {
        // 以温度为排序依据的小顶堆,温度越低越靠前
        PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.temperature));
        for (int index = 0; index < T.length; index++) {
            Node node = new Node();
            node.temperature = T[index];
            node.index = index;
            // 放入队列中
            queue.add(node);
            // 取队列中最小的元素
            Node newNode = queue.peek();
            // 如果队列中最低温度就是当前温度
            if (newNode.temperature == node.temperature) {
                // 说明queue中没有比当前温度低的天
                continue;
            }

            // 最低温度比当前低,满足情况
            while (newNode.temperature < node.temperature) {
                // 更新T,并且移除
                T[newNode.index] = node.index - newNode.index;
                queue.remove();
                newNode = queue.peek();
            }
        }

        // 队列中剩余的节点,都对应0
        Iterator<Node> iterator = queue.iterator();
        while (iterator.hasNext()) {
            Node node = iterator.next();
            T[node.index] = 0;
        }
        
        return T;
    }

    class Node {
        int temperature;
        int index;
    }
}

提交OK,时间复杂度为O(n),但小顶堆的更新也是需要时间的,因此还是有可以优化的地方。

数组

因为题目中给出了:每个气温的值的均为华氏度,都是在 [30, 100] 范围内的整数,所以我们可以用一个长度为100的数组存储气温对应的天数。

这样我们就需要从后向前遍历了,将气温对应的天数记录在数组中,这样每向前遍历一个,就遍历一次这个长度为100的数组,如果有比当前温度高的,则更新结果,否则就记为0。

虽然每次都要遍历一次长度为100的数组,但因为数组查询的时间复杂度为O(1),所以速度是很快的。接下来我们看看代码:

class Solution {
    public int[] dailyTemperatures(int[] T) {
        // 最终结果
        int[] result = new int[T.length];
        // 因为温度不超过100度,所以温度对应的天数存储在这个数组中
        int[] next = new int[101];
        Arrays.fill(next, Integer.MAX_VALUE);
        // 从后向前遍历
        for (int i = T.length - 1; i >= 0; --i) {
            // 比当前温度更高的下标
            int warmerIndex = Integer.MAX_VALUE;
            // 从next数组中查找比当前温度高的天数
            for (int t = T[i] + 1; t <= 100; ++t) {
                // 找出天数最小的一个
                if (next[t] < warmerIndex) {
                    warmerIndex = next[t];
                }
            }
            // 如果有找到,则更新result
            if (warmerIndex < Integer.MAX_VALUE) {
                result[i] = warmerIndex - i;
            }
            // 在next数组中记录当前的温度
            next[T[i]] = i;
        }
        return result;
    }
}

提交OK,这里其实就够了,但有没有其他更方便的数据结构呢?

我们主要想知道的,就是最近的比当前温度高的天数,这样的需求,感觉栈应该是可以满足的,因为先进后出。

我们还是从后向前遍历,在栈中存储气温的天数,当前遍历到的温度,如果比栈顶的存储的天数对应的温度高,那么栈中存储的是没有意义的;如果比它低,那么就可以更新结果了。

接下来看看代码:

class Solution {
    public int[] dailyTemperatures(int[] T) {
        // 用栈存储温度的下标
        Stack<Integer> stack = new Stack<>();
        // 最终的结果
        int[] result = new int[T.length];
        // 从后向前遍历
        for (int i = T.length - 1; i >= 0; i--) {
            // 如果当前温度大于栈顶的温度
            while (!stack.isEmpty() && T[i] >= T[stack.peek()]) {
                // 因为当前温度比栈顶存储的温度高,
                // 栈顶元素也没有存储的意义,所以出栈
                stack.pop();
            }
            // 如果栈为空,则结果为0
            // 如果栈不为空,则用当前栈顶存储的温度
            result[i] = stack.isEmpty() ? 0 : (stack.peek() - i);
            // 让当前的温度入栈
            stack.push(i);
        }

        return result;
    }
}

提交OK,时间复杂度和上面的方法相同,但空间复杂度理论上是会比上面小的。

总结

以上就是这道题目我的解答过程了,不知道大家是否理解了。这道题主要是找规律,优化的时候可以利用数据结构的特性(数组和栈)。

有兴趣的话可以访问我的博客或者关注我的公众号、头条号,说不定会有意外的惊喜。

https://death00.github.io/

公众号:健程之道

力扣739——每日温度

力扣739——每日温度

点赞
收藏
评论区
推荐文章
美凌格栋栋酱 美凌格栋栋酱
7个月前
Oracle 分组与拼接字符串同时使用
SELECTT.,ROWNUMIDFROM(SELECTT.EMPLID,T.NAME,T.BU,T.REALDEPART,T.FORMATDATE,SUM(T.S0)S0,MAX(UPDATETIME)CREATETIME,LISTAGG(TOCHAR(
Aimerl0 Aimerl0
4年前
每日一题(一)
写在前面刷题在北联大的BUU平台,每日一题,每日更新,嘿嘿HCTF2018WarmUp刚开始看这个题真的一点思路没有,看源码、抓包一波操作过后还是选择去找了wp。。。wp说原题是有个hint.php,扫目录也可以扫出source.phphint.php里面说真正的flag文件是ffffllllaaaagggg里source.php里面是源码,代码审
如何实现千万级优惠文章的优惠信息同步
金融社区优惠文章是基于京东商城优惠商品批量化自动生成的,每日通过不同的渠道获取到待生成的SKU列表,并根据条件生成优惠文章。
Aimerl0 Aimerl0
4年前
每日一题(三)
写在前面不知道Web的每日一题还能坚持多久,做到以前那种大比赛的Web题时发现一天时间很难吃透,或者根本就是一天时间内搞不懂,还听协会里的pwn师傅说一道pwn题能打三四天,一个星期,所以可能以后每日一题往各个方向的基础题发展,下一步准备把固态买回来重装一遍系统,然后进军pwn!!!极客大挑战2019BuyFlag进入pay.p
卡尔 卡尔
4年前
当裸辞遇到了面试难,你需要了解一下这些面试题
乘兴裸辞心甚爽,面试工作屡遭难。幸得每日一题伴,点击关注莫偷懒。又要到金九银十的跳槽季了,为了让更多的小伙伴可以在面试的时候取的更好的offer,所以自上月起我每天都会在自己的公众号【前端有的玩】里面推送一到两道面试题,俗称每日一题(每日一坑)。方便找工作的小伙伴每日都会有新的收获。本文就是小编将前期的一些比较经典的每日一题进行了梳理,欢迎大家一起
Stella981 Stella981
3年前
AssemblyScript 入门指南[每日前端夜话0xEB]
每日前端夜话0xEB每日前端夜话,陪你聊前端。每天晚上18:00准时推送。正文共:2459 字预计阅读时间:10分钟作者:DannyGuo翻译:疯狂的技术宅来源:logrocket!(https://oscimg.oschina.net/oscnet/b880277c594152a503
Stella981 Stella981
3年前
Nginx数据结构之散列表
1\.散列表(即哈希表概念)散列表是根据元素的关键码值而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找速度。这个映射函数f叫做散列方法,存放记录的数组叫做散列表。若结构中存在关键字和K相等的记录,则必定在f(K)的存储位置上。由此,不需要比较便可直接取得所
Stella981 Stella981
3年前
Node.js 12中的ES模块[每日前端夜话0x9E]
每日前端夜话0x9E每日前端夜话,陪你聊前端。每天晚上18:00准时推送。正文共:2552字预计阅读时间:10 分钟作者:BrianDeSousa翻译:疯狂的技术宅来源:logrocket!(https://oscimg.oschina.net/oscnet/2ccaf94cecd3
贾蔷 贾蔷
3个月前
力扣1137题 解题思路和步骤 C++代码实现,力扣一共多少题
一、题目分析力扣1137题要求我们找到第N个泰波那契数。泰波那契数的定义是:T00,T11,T21,且在n0的条件下Tn3TnTn1Tn2。,当n4时,T4T3T2T14。这道题主要考查我们对递归或动态规划的理解和运用。在思考解题方法时,我们
贾蔷 贾蔷
3个月前
力扣746:三步通关最小花费爬楼梯
题目解析:站在楼梯的某个台阶时,需要支付当前台阶对应的体力值costi,之后可以选择向上爬1或2个台阶。最终目标是到达‌楼层顶部‌(即数组末尾之后的位置),且初始位置可选择下标0或1的台阶作为起点。要求找出到达顶部的‌最小花费路径‌。例如输入cost
深度学习 深度学习
3星期前
牛客4579题:钓鱼比赛——概率计算与比较
一、题目解读4579题要求解决一个基于网格的问题:给定一个n×m的,每个元素表示对应位置钓到鱼的概率。用户需根据输入的坐标(x,y)和尝试次数t,比较该位置钓到鱼的累积概率与全区域平均概率的累积概率,并输出结果("equal"、"cc"或"ss")。题目强