教你快速找到及时序列的最小值

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

（编辑：好传媒网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!