博客
关于我
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/

    你可能感兴趣的文章
    QT教程2:QT5的体系构架
    查看>>
    PON架构(全光网络)
    查看>>
    PoolingHttpClientConnectionManager原理剖析
    查看>>
    QT教程1:ubuntu18.04安装QT5
    查看>>
    POP-一个点击带有放大还原的动画效果
    查看>>
    POP3 协议在计算机网络中的优缺点
    查看>>
    qt批量操作同类型控件
    查看>>
    Portaudio笔记-WASAPI
    查看>>
    position:fixed失效情况
    查看>>
    Qt开发笔记:QGLWidget、QOpenGLWidget详解及区别
    查看>>
    Position属性四个值:static、fixed、absolute和relative的区别和用法
    查看>>
    POSIX thread编程中关于临界区内条件变量的分析
    查看>>
    POSIX与程序可移植性
    查看>>
    posix多线程有感--自旋锁
    查看>>
    SpringBoot中集成海康威视SDK实现布防报警数据上传/交通违章图片上传并在linux上部署(附示例代码资源)
    查看>>
    POSIX标准和XSI扩展
    查看>>
    post install error,please remove node_moules before retry
    查看>>
    postcss-pxtorem 参数之selectorBlackList、exclude的用法
    查看>>
    Postek博思得标签打印机更换电脑,打印出来标签空白
    查看>>
    postfix+ dovecot搭建邮件服务器
    查看>>