最小栈
最小栈，能在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
最新文章
热门文章
猜你喜欢
