最小棧

最小棧，能在O(1)內找到棧內序列的最小值，因此此特性經常用于提升算法性能。下面看看它的一種實現。

[[395237]]

分析過程

入棧分析：

推入元素到 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]]