Leetcode 包含min函数的栈

leetcode

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

思路

方法一：辅助栈同步
可以多开一个栈，来储存最小值，每次新数据进栈时，和之前的最小值进行比较，如果小于，则压入栈，否则，压入之前的最小值。
保持最小值栈和数据栈的长度一致，进栈出栈的操作要同步。

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.min_stack = []

    def push(self, x: int) -> None:
        self.stack.append(x)
        if len(self.min_stack)==0 or self.min_stack[-1] >x:
            self.min_stack.append(x)
        else:
            self.min_stack.append(self.min_stack[-1])

    def pop(self) -> None:
        if self.stack:
            self.stack.pop()
            self.min_stack.pop()
        
    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        if self.min_stack:
            return self.min_stack[-1]

方法二：辅助栈不同步
在弹出时，考虑如果弹出值为最小值，那么储存最小值的栈也需要弹出，否则只有数据栈弹出

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack =[]
        self.tmp = []

    def push(self, x: int) -> None:
        self.stack.append(x)
        if len(self.tmp)==0 or self.tmp[-1] >=x:
            self.tmp.append(x)
        

    def pop(self) -> None:
        if not self.stack:
            return 
        if self.stack[-1] == self.tmp[-1]:
            self.stack.pop()
            self.tmp.pop()
        else:
            self.stack.pop()

    def top(self) -> int:
        if self.stack:
            return self.stack[-1]

    def getMin(self) -> int:
        if self.tmp:
            return self.tmp[-1]