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

发布时间:2021-09-17 14:20:08 作者:柒染
来源:亿速云 阅读:135

如何在O(1)内找到实时序列的最小值,针对这个问题,这篇文章详细介绍了相对应的分析和解答,希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。

最小栈

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

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

分析过程

入栈分析:

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

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

出栈分析:

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

这道题需要注意两点:

代码

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]]

关于如何在O(1)内找到实时序列的最小值问题的解答就分享到这里了,希望以上内容可以对大家有一定的帮助,如果你还有很多疑惑没有解开,可以关注亿速云行业资讯频道了解更多相关知识。

推荐阅读:
  1. 在O(1)时间删除链表结点——13
  2. 在O(1)时间删除链表节点

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

上一篇:.net如何读写xml文档

下一篇:xml语法的示例分析

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》