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

时间:2021-05-02

最小栈

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

分析过程

入栈分析:

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

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

出栈分析:

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

这道题需要注意两点:

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

代码

  • classMinStack(object):
  • def__init__(self):
  • """
  • initializeyourdatastructurehere.
  • """
  • self.mainstack=[]
  • self.tmpstack=[]
  • 推入元素:

  • defpush(self,val):
  • """
  • :typeval:int
  • :rtype:None
  • """
  • self.mainstack.append(val)
  • ifnotself.tmpstack:
  • self.tmpstack.append(len(self.mainstack)-1)
  • #smallerthantopoftmpstack
  • ifself.mainstack[self.tmpstack[-1]]>val:
  • self.tmpstack.append(len(self.mainstack)-1)
  • 出栈元素:

  • defpop(self):
  • """
  • :rtype:None
  • """
  • #minvaloftmpstackequalstopofmainstack
  • ifself.tmpstackandself.tmpstack[-1]==len(self.mainstack)-1:
  • self.tmpstack.pop()
  • returnself.mainstack.pop()
  • deftop(self):
  • """
  • :rtype:int
  • """
  • ifself.mainstack:
  • returnself.mainstack[-1]
  • 使用tmpstack辅助栈,换来了O(1)的查询最小复杂度

  • defgetMin(self):
  • """
  • :rtype:int
  • """
  • ifself.tmpstack:
  • returnself.mainstack[self.tmpstack[-1]]
  • 原文地址:https://mp.weixin.qq.com/s?__biz=MzI3NTkyMjA4NA==&mid=2247501647&idx=1&sn=347e57b8a560459398d4d0cef5d9fb1d&chksm=eb7fea84dc086392e7e0fc22e2f2bd8457db7dab4a0ef318b3f7ac1c2adf7adf6f1fbbad170d&mpshare=1&s

    声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

    相关文章