155 Min Stack

题目

Min Stack

题解

题目要求执行push、pop和min操作的时间复杂度必须为\(O(1)\)，所以搜索整个栈找出最小值的做法是不可行的，必须在执行push/pop操作时就记录下栈当前的最小值。

一个简单的做法是在栈里维护一个min变量，每次执行push操作时把当前的min（\(min(当前栈中的最小值，准备入栈的数据)\)）和数据值一起压入栈中，执行pop操作时则用新的栈顶元素中记录的min值维护min变量。然而这种方法会使得每个栈中的元素都要记录一个min值，可能会浪费许多空间。

一种更好的方法是另外使用一个栈min_stack来记录min数据，每次执行min操作时都返回min_stack的栈顶数据（若min_stack为空则返回整数最大值）。每次执行push/pop操作时，根据入栈/出栈的数据和当前min返回结果的大小关系来相应地更新min_stack。这样就能省下许多记录重复min值的空间，但是这里有一种特殊情况，那就是所有的值都是最小值。这种情况下是不会节省空间的，因为min_stack必须存储跟当前数据栈相同数量的最小值（例如，如果当前数据栈中的最小值为m，且数据栈中有n个m，那么min_stack中也应该有n个m），不然一个pop操作之后min_stack就变成空栈了，这也是为什么下面代码中push函数里的if条件是val <= self.getMin()而不是val < self.getMin()。

代码

class MinStack:

    def __init__(self):
        self.value_stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.value_stack.append(val)
        if val <= self.getMin():
            self.min_stack.append(val)

    def pop(self) -> None:
        val = self.value_stack.pop()
        if val == self.getMin():
            self.min_stack.pop()

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

    def getMin(self) -> int:
        if len(self.min_stack) > 0:
            return self.min_stack[-1]
        else:
            return sys.maxsize