博客
关于我
LeetCode0739. 每日温度
阅读量:307 次
发布时间:2019-03-03

本文共 518 字,大约阅读时间需要 1 分钟。

一. 题目
  • 题目: 给定一个温度数组,计算每个元素比前面较大的元素的差值
  • 二. 方法一: 单调栈
  • 解题步骤

  • 解题代码示例

    def dailyTemperatures(self, T: List[int]) -> List[int]:    stack = []    result = [_ for _ in T]    for index in range(len(T)):        while stack and T[index] > T[stack[-1]]:            result[stack[-1]] = index - stack[-1]            stack.pop()        stack.append(index)    for ele in stack:        result[ele] = 0    return result
  • 时间复杂度: O(n)

  • 空间复杂度: O(n)

  • 三. 优化说明
    本文采用单调栈算法,通过维护一个递减序列来记录温度数组中每个元素的前驱元素索引,从而计算出每个元素与前驱元素的差值。该算法在时间和空间复杂度均为O(n)的前提下,高效解决了问题。

    转载地址:http://pjum.baihongyu.com/

    你可能感兴趣的文章
    posix多线程有感--自旋锁
    查看>>
    POSIX标准和XSI扩展
    查看>>
    postgres--流复制
    查看>>
    postgres10配置huge_pages
    查看>>
    PostgreSQL 10.0 preview 变化 - pg_xlog,pg_clog,pg_log目录更名为pg_wal,pg_xact,log
    查看>>
    PostgreSQL 10.1 手册_部分 II. SQL 语言_第 15章 并行查询_15.2. 何时会用到并行查询?...
    查看>>
    PostgreSQL 10.1 手册_部分 II. SQL 语言_第 9 章 函数和操作符_9.23. 行和数组比较
    查看>>
    PostgreSQL 10.1 手册_部分 III. 服务器管理_第 21 章 数据库角色
    查看>>
    Postgresql 12.9如何配置允许远程连接
    查看>>
    PostgreSQL 9.6 同步多副本 与 remote_apply事务同步级别 应用场景分析
    查看>>
    Postgresql CopyManager 流式批量数据入库
    查看>>
    PostgreSQL cube 插件 - 多维空间对象
    查看>>
    PostgreSQL Daily Maintenance - cluster table
    查看>>
    PostgreSQL on Linux 最佳部署手册
    查看>>
    PostgreSQL Oracle 兼容性之 - pipelined
    查看>>
    PostgreSQL Point-In-Time Recovery (Incremental Backup)
    查看>>
    postgresql Streaming Replication监控与注意事项
    查看>>
    postgresql 不需要付费_使用数据传输在PostgreSQL执行 外部连接运算符
    查看>>
    postgresql 主从配置_生产环境postgresql主从环境配置
    查看>>
    postgresql 函数&存储过程 ; 递归查询
    查看>>