专栏首页算法channel如何在O(1)内找到实时序列的最小值?

如何在O(1)内找到实时序列的最小值?

最小栈

最小栈,能在O(1)内找到栈内序列的最小值,因此此特性经常用于提升算法性能。下面看看它的一种实现。

分析过程

  1. 入栈分析:

推入元素到 mainstack,只有当当前元素小于tmpstack栈顶(实际存储为mainstack中元素索引)元素时,才入栈到tmpstack,入栈的是索引。

假设mainstack当前有n个元素,则tmpstack内元素至多有n个。等于n时,表明原入栈序列为单调递减序列。

  1. 出栈分析:

元素从mainstack出栈,但要注意出栈元素索引是否等于tmpstack栈顶,若是需要将tmpstack栈顶元素出栈。可以预知,栈顶索引一定小于等于出栈元素(在mainstack栈内)的索引。

这道题需要注意两点:

  1. 临时栈里推送的是主栈的元素索引
  2. push时若临时栈为空,需要先推入此元素在主栈索引

代码

class MinStack(object):
    def __init__(self):

        """
        initialize your data structure here.
        """
        self.mainstack= []
        self.tmpstack = []

推入元素:

    def push(self, val):

        """
        :type val: int
        :rtype: None
        """

        self.mainstack.append(val)

        if not self.tmpstack:

            self.tmpstack.append(len(self.mainstack)-1)

        # smaller than top of tmpstack
        if self.mainstack[self.tmpstack[-1]] > val:

            self.tmpstack.append(len(self.mainstack)-1) 

出栈元素:

    def pop(self):
        """
        :rtype: None
        """

        # min val of tmp stack equals top of mainstack
        if self.tmpstack and self.tmpstack[-1] == len(self.mainstack)-1:
            self.tmpstack.pop()

        return self.mainstack.pop()

   def top(self):
       """
       :rtype: int
       """

       if self.mainstack:
           return self.mainstack[-1]

使用tmpstack辅助栈,换来了O(1)的查询最小复杂度

    def getMin(self):
        """
        :rtype: int
        """

        if self.tmpstack:
            return self.mainstack[self.tmpstack[-1]]

本文分享自微信公众号 - Python与机器学习算法频道(alg-channel),作者:zhenguo

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-04-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 吴师兄导读:如何快速入门数据结构和算法

    吴师兄导读:有哪些常见的数据结构?基本操作是什么?常见的排序算法是如何实现的?各有什么优缺点?本文简要分享算法基础、常见的数据结构以及排序算法,给同学们带来一堂...

    五分钟学算法
  • 前端进阶必备 — 手撕排序算法

    算法(Algorithm) 代表着用系统的方法描述解决问题的策略机制,可以通过一定规范的 输入,在有限时间内获得所需要的 输出。

    用户1462769
  • 【算法入门】用Python手写五大经典排序算法,看完这篇终于懂了!

    算法作为程序员的必修课,是每位程序员必须掌握的基础。作为Python忠实爱好者,本篇将通过Python来手撕5大经典排序算法,结合例图剖析内部实现逻辑,对比每种...

    黄博的机器学习圈子
  • 八大排序算法总结与java实现

    因为健忘,加上对各种排序算法理解不深刻,过段时间面对排序就蒙了。所以决定对我们常见的这几种排序算法进行统一总结,强行学习。首先罗列一下常见的十大排序算法:

    林老师带你学编程
  • 面试汇总(九):数据结构与算法常见面试总结(二)——堆与栈、数组、排序

      上一篇文章我们介绍了在面试中数据结构中树的常见的面试题。这篇文章我们继续给大家介绍常见的问题。

    一计之长
  • Serverless最佳实践:如何在两周内开发出用户量过亿的微信小程序

    腾讯相册前身是空间相册,而且空间相册已经在手机APP端,网页端都有了入口。为了增加用户活跃,让客户在各个软件中都能快速触达,腾讯相册团队推出了微信小程序形式的腾...

    腾讯云serverless团队
  • 如果有人问你数据库的原理,叫他看这篇文章-1

    国内大佬翻译的文章,因为文章较长,不适合碎片化阅读,因此分为几篇文章来转载,满满的干货,外链在微信上不能显示

    Java识堂
  • 十大经典排序算法 -- 动图讲解

    外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;

    互扯程序
  • 数组:滑动窗口拯救了你

    给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组,并返回其长度。如果不存在符合条件的子数组,返回 0...

    代码随想录

扫码关注云+社区

领取腾讯云代金券