如何在O(1)内找到实时序列的最小值？
最小栈
最小栈，能在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]]
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-04-22，如有侵权请联系 cloudcommunity@tencent.com 删除
本文分享自 程序员郭震zhenguo 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ，欢迎热爱写作的你一起参与！
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
