如何在O(1)内找到实时序列的最小值?
2023-03-09 22:11:24 时间
最小栈
最小栈,能在O(1)内找到栈内序列的最小值,因此此特性经常用于提升算法性能。下面看看它的一种实现。
分析过程
入栈分析:
推入元素到 mainstack,只有当当前元素小于tmpstack栈顶(实际存储为mainstack中元素索引)元素时,才入栈到tmpstack,入栈的是索引。
假设mainstack当前有n个元素,则tmpstack内元素至多有n个。等于n时,表明原入栈序列为单调递减序列。
出栈分析:
元素从mainstack出栈,但要注意出栈元素索引是否等于tmpstack栈顶,若是需要将tmpstack栈顶元素出栈。可以预知,栈顶索引一定小于等于出栈元素(在mainstack栈内)的索引。
这道题需要注意两点:
- 临时栈里推送的是主栈的元素索引
- 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]]
相关文章
- 数据孤岛是业务效率的无声杀手
- 2023展望:新的一年将给大数据分析领域带来什么?
- 阿里云ADB基于Hudi构建Lakehouse的实践
- 大数据在医疗保健领域的使用案例
- 微软增加说明:KB5021751 更新扫描已经 / 即将过时 Office 过程中不会触碰用户隐私
- 2022 Gartner全球云数据库管理系统魔力象限发布 腾讯云数据库入选
- 场景化、重实操,分享一个实时数仓实践案例
- Arctic的湖仓一体践行之路
- 分布式计算MapReduce究竟是怎么一回事?
- 淘系数据模型治理优秀实践
- 大数据分析对医疗保健的影响
- 当我们说大数据Hadoop,究竟在说什么?
- 2022年及以后大数据的五个发展趋势
- 网易严选离线数仓治理实践
- 2023 年数据治理趋势
- 一份“靠谱”的年度经营计划,你学会了吗?
- 漫谈对大数据的思考
- 测试一下,读懂数据的能力,你有吗?
- 用艺术的眼光探索数据之美
- 聊聊数据分析成果如何落地