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

相关文章

来自专栏计算机视觉与深度学习基础

Leetcode 162 Find Peak Element

A peak element is an element that is greater than its neighbors. Given an inpu...

1927
来自专栏乐沙弥的世界

CRS-1006 , CRS-0215 故障一例

    安装好sles 10 sp3 + Oracle 10g RAC之后,在配置监听器时,总是提示主机bo2dbp上的监听服务已经在运行,忽略错误之后手动在b...

463
来自专栏我是业余自学C/C++的

sprintf_s的使用

1222
来自专栏算法修养

PAT 1013 Battle Over Cities(并查集)

1013. Battle Over Cities (25) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 ...

2836
来自专栏Bingo的深度学习杂货店

Q171 Excel Sheet Column Number

Related to question Excel Sheet Column Title Given a column title as appear in a...

3275
来自专栏Petrichor的专栏

leetcode: 36. Valid Sudoku

1053
来自专栏cs

ASP.NET 数据库访问

新建数据,采用sql server数据库 use dflx; create table person --建立表 ( name char(12), ...

3436
来自专栏数据结构与算法

agc001E - BBQ Hard(dp 组合数)

首先,我们可以把\(C_{a_i + b_i + a_j + b_j}^{a_i + a_j}\)看做从\((-a_i, -b_i)\)走到\((a_j, b_...

671
来自专栏杨建荣的学习笔记

使用shell进行日志分析(r2第14天)

最近做数据批量加载的时候,是通过pl/sql嵌在shell脚本里执行的。 脚本运行后生成的日志类似如下的格式 Get Dump file for APP_TM...

3136
来自专栏乐沙弥的世界

Oracle 11g RAC crs_stat 命令结果完整显示

Oracle 11g RAC中crs_stat命令较之前的版本多出了很多新的不同的资源类型,缺省情况下,使用crs_stat -t来查看资源是密密麻麻一大片,看...

1271

扫码关注云+社区