如何在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