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 条评论
登录 后参与评论

相关文章

来自专栏张坤的专栏

基于Http原理实现Android的图片上传和表单提交

Java的HttpURLConnection没有这么简单的封装形式,需要完整的Request Payload模拟,用起来相对不方便,不过这样能够对表单提交的原理...

2K0
来自专栏【转载】DRF+Vue+Mysql_生鲜超市系统

五、商品列表页

在goods文件夹下面新建view_base.py,为了区分django和django rest framework的view

100
来自专栏前端架构

详解XML(扩展标记语言 (Extensible Markup Language, XML))

扩展标记语言 (Extensible Markup Language, XML) ,用于标记电子文件使其具有结构性的标记语言,可以用来标记数据、定义数据类型,是...

371
来自专栏LeoXu的博客

[翻译]Ext JS 教程-ExtJS 4中的数据包(Package)

数据包(data package)是用来加载和保存你应用程序中的数据的东西,包含41个类,但是其中有三个类比所有其他类更加重要——Model,Store和Ext...

812
来自专栏Python

Python 实现抽象类的两种方式+邮件提醒+动态导入模块+反射(参考Django中间件源码)

实现抽象类的两种方式 方式一 from abc import ABCMeta from abc import abstractmethod class Bas...

2045
来自专栏有趣的django

Django REST framework+Vue 打造生鲜超市(四)

五、商品列表页 5.1.django的view实现商品列表页 (1)goods/view_base.py 在goods文件夹下面新建view_base.py,为...

1.1K9
来自专栏一“技”之长

iOS UISegmentedControl 原

SegmentedControl又被称作分段控制器,是IOS开发中经常用到的一个UI控件。

856
来自专栏张善友的专栏

Quartz.net官方开发指南 第四课:关于Triggers更多内容

同Job一样,trigger非常容易使用,但它有一些可选项需要注意和理解,同时,trigger有不同的类型,要按照需求进行选择。 Calendars——日历 ...

1818
来自专栏Urahara Blog

Joomla V3.7.0 核心组件SQL注入漏洞分析

1574
来自专栏蛋未明的专栏

javascript前端XML格式正确性验证方法

2175

扫码关注云+社区