当前位置： 当前位置：首页 >数据库 >如何在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]] 源码下载