最小栈

最小栈

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 x  None:
        if self.stack:
            self.stack.pop()
            return self.min_stack.pop()

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

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

2、辅助栈和数据栈不同步

class MinStack:
    # 辅助栈和数据栈不同步
    # 关键 1：辅助栈的元素空的时候，必须放入新进来的数
    # 关键 2：新来的数小于或者等于辅助栈栈顶元素的时候，才放入（特别注意这里等于要考虑进去）
    # 关键 3：出栈的时候，辅助栈的栈顶元素等于数据栈的栈顶元素，才出栈，即"出栈保持同步"就可以了

 

    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 x  None:
        top = self.stack.pop()
        #关键 3：出栈的时候，辅助栈的栈顶元素等于数据栈的栈顶元素，才出栈，即"出栈保持同步"就可以了
        if self.min_stack and top == self.min_stack[-1]:
            self.min_stack.pop()
         return top

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

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