Min Stack

要想O(1)时间只有一个办法，照牛客网里面说的用双栈，一个栈放数据，一个栈放当前最小值

class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.store = []
        self.minStore = []
        self.curMin = sys.maxint

    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        self.store.append(x)
        self.curMin = min(self.curMin, x)
        self.minStore.append(self.curMin)

    def pop(self):
        """
        :rtype: void
        """
        self.store.pop()
        self.minStore.pop()
        self.curMin = self.minStore[-1] if self.minStore else sys.maxint

    def top(self):
        """
        :rtype: int
        """
        return self.store[-1]

    def getMin(self):
        """
        :rtype: int
        """
        return self.minStore[-1]

还有一种单栈就可以实现查最小值的方法，当压入元素不大于当前最小值时，当前最小值先被压入，再压入输入元素，这样保证了top操作只需要返回栈顶元素就是正确的，getmin操作也是一样，同时pop时如果pop元素等于最小值，那说明这个值压入时一起压入了它之前的一个最小值进栈，这时我们再pop一个数到min变量上就是pop这个元素之后栈的最小值了，稍微有点点绕，但是是个很巧妙的方法

class MinStack(object):

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

    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        if x <= self.min:
            self.stack.append(self.min)
            self.min = x
        self.stack.append(x)

    def pop(self):
        """
        :rtype: void
        """
        if self.stack.pop() == self.min:
            self.min = self.stack.pop()

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

    def getMin(self):
        """
        :rtype: int
        """
        return self.min