栈 问题

155. 最小栈

常数时间内检索最小元素

使用一个辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值。【示意图】

• 当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中；
• 当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出；
• 在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中。

时间复杂度 O₍₁₎ 空间复杂度 O_(n)

class MinStack:

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

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.minval_stack or x <= self.minval_stack[-1]:
            self.minval_stack.append(x)

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


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

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