个人中心
gpt4 book ai didi

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

转载 作者：qq735679552 更新时间：2022-09-27 22:32:09 24 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章如何在O(1)内找到实时序列的最小值？由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

最小栈 。

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

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

分析过程 。

入栈分析:

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

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

出栈分析:

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

这道题需要注意两点:

  • 临时栈里推送的是主栈的元素索引
  • push时若临时栈为空，需要先推入此元素在主栈索引

代码 。

  1. class MinStack(object): 
  2.     def __init__(self): 
  3.  
  4.         """ 
  5.         initialize your data structure here. 
  6.         """ 
  7.         self.mainstack= [] 
  8.         self.tmpstack = [] 

推入元素:

  1. def push(self, val): 
  2.  
  3.     """ 
  4.     :type val: int 
  5.     :rtype: None 
  6.     """ 
  7.  
  8.     self.mainstack.append(val) 
  9.  
  10.     if not self.tmpstack: 
  11.  
  12.         self.tmpstack.append(len(self.mainstack)-1) 
  13.  
  14.     # smaller than top of tmpstack 
  15.     if self.mainstack[self.tmpstack[-1]] > val: 
  16.  
  17.         self.tmpstack.append(len(self.mainstack)-1)  

出栈元素:

  1. def pop(self): 
  2.     """ 
  3.     :rtype: None 
  4.     """ 
  5.  
  6.     # min val of tmp stack equals top of mainstack 
  7.     if self.tmpstack and self.tmpstack[-1] == len(self.mainstack)-1: 
  8.         self.tmpstack.pop() 
  9.  
  10.     return self.mainstack.pop() 
  1. def top(self): 
  2.     """ 
  3.     :rtype: int 
  4.     """ 
  5.  
  6.     if self.mainstack: 
  7.         return self.mainstack[-1] 

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

  1. def getMin(self): 
  2.     """ 
  3.     :rtype: int 
  4.     """ 
  5.  
  6.     if self.tmpstack: 
  7.         return self.mainstack[self.tmpstack[-1]] 

原文地址：https://mp.weixin.qq.com/s?__biz=MzI3NTkyMjA4NA==&mid=2247501647&idx=1&sn=347e57b8a560459398d4d0cef5d9fb1d&chksm=eb7fea84dc086392e7e0fc22e2f2bd8457db7dab4a0ef318b3f7ac1c2adf7adf6f1fbbad170d&mpshare=1&s 。

最后此篇关于如何在O(1)内找到实时序列的最小值？的文章就讲到这里了,如果你想了解更多关于如何在O(1)内找到实时序列的最小值？的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

24 4 0
文章推荐： 一篇带给你ClickHouse集群搭建
文章推荐： java web SpringMVC后端传json数据到前端页面实例代码
文章推荐： 深入讲解java线程与synchronized关键字
文章推荐： 200个Python 标准库总结分享(建议收藏)
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com