LWC 61:739. Daily Temperatures

LWC 61:739. Daily Temperatures

传送门:739. Daily Temperatures

Problem:

Given a list of daily temperatures, produce a list that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead. For example, given the list temperatures = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note:

The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

思路: 求出当前元素的第一个大于它的位置即可,所以该问题就是nextGreaterElement系列,具体参考博文【 算法细节系列(10):503. Next Greater Element II

Java版本:

    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] ans = new int[n];

        Stack<Integer> stack = new Stack<>();
        Map<Integer, Integer> mem = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
                int nxt = stack.pop();
                mem.put(nxt, i);
            }
            stack.push(i);
        }

        for (int i = 0; i < n; ++i) {
            if (mem.containsKey(i)) {
                ans[i] = mem.get(i) - i;
            }
            else ans[i] = 0;
        }

        return ans;
    }

Python 版本:

    def dailyTemperatures(self, temperatures):
        """
        :type temperatures: List[int]
        :rtype: List[int]
        """
        n = len(temperatures)
        stack = []
        map = {}

        ans = [0] * n
        for i in range(n):
            while (len(stack) > 0 and temperatures[stack[-1]] < temperatures[i]):
                nxt = stack.pop(-1)
                ans[nxt] = i - nxt
            stack.append(i)

        return ans  

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏微信公众号:Java团长

JavaSE入门篇:程序结构

二、选择结构:从名字就能看出,要选择嘛,到底是要漂亮滴妹子,还是要有钱滴妹子呢!当然,如果是个吊丝码农滴话,那你就不要多想了,还是老老实实码代码吧···

15530
来自专栏林冠宏的技术文章

java 连接数据库之一个完整的函数

第一个参数要查询的列名 第二个参数是连接的url 第三个参数是用户名 第四个参数密码 第五个参数是执行的命令。 注意,url格式是 jdbc:mysql://l...

19580
来自专栏魂祭心

原 What Every Dev need

29780
来自专栏python3

python 装饰器案例解析

执行的时候,不能写deco(test1()),为什么呢?这样写,是把test1函数执行的结果,传给deco了。

9010
来自专栏熊二哥

快速入门系列--CLR--03泛型集合

.NET中的泛型集合 在这里主要介绍常见的泛型集合,很多时候其并发时的线程安全性常常令我们担忧。因而简述下.NET并发时线程安全特性,其详情请见MSDN。 ...

18870
来自专栏GreenLeaves

Decorator装饰者模式(结构型模式)

假设让我们去设计FCL中的Stream类,该类具有流类的基本功能,除了有各种不同类型的流外(如内存流、文件流、网络流等等),但是在不同的业务场景下,如处理银行业...

8220
来自专栏软件开发 -- 分享 互助 成长

sizeof(数组)

这里就不讨论一般的数组长度计算了,只说明一下任何数据到了函数的形参中都将退化为指针,所以计算大小的时候,也是计算的指针的大小 直接上代码了 1 // clas...

29980
来自专栏py+selenium

[笨方法学python]习题51自动化测试笔记

本节自动化测试部分看不大懂,自己每步都打印出来,帮助理解。(代码标红部分为自己加入调试为打印变量值所用)

28520
来自专栏黑泽君的专栏

【小知识】小例子说明Spring的核心思想之一:控制反转。

目的:改写已存在的类的某个方法或某些方法,使方法增强了。装饰设计模式(也即包装设计模式) 口诀:

19510
来自专栏康怀帅的专栏

PHP 变量与常量

本文介绍了 PHP 变量与常量。 官方文档:http://php.net/manual/zh/language.variables.php 官方文档:http:...

31640

扫码关注云+社区

领取腾讯云代金券