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

相关文章

来自专栏康怀帅的专栏

PHP 变量与常量

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

2674
来自专栏学习力

《Java从入门到放弃》JavaSE入门篇:程序结构 推荐

1584
来自专栏python3

python 装饰器案例解析

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

711
来自专栏学习力

《Java从入门到放弃》框架入门篇:Struts2的常用验证方式(二)

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

sizeof(数组)

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

2358
来自专栏CDA数据分析师

学完Python基础知识后,你真的会python吗?

前言 最近觉得 Python 太“简单了”,于是在师父川爷面前放肆了一把:“我觉得 Python 是世界上最简单的语言!”。于是川爷嘴角闪过了一丝轻蔑的微笑(内...

29710
来自专栏小樱的经验随笔

对X86汇编的理解与入门

本文描述基本的32位X86汇编语言的一个子集,其中涉及汇编语言的最核心部分,包括寄存器结构,数据表示,基本的操作指令(包括数据传送指令、逻辑计算指令、算数运算指...

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

JavaSE入门篇:程序结构

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

1043
来自专栏小狼的世界

Linux下不同文件编码的转换

字符编码(Character Encoding)可以说就是让某一字符序列匹配一个指定集合中的某一东西,常见的例子包括长短电键组合起来表示的摩斯电码(Morse ...

602
来自专栏py+selenium

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

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

1302

扫码关注云+社区