Min Stack

Implement a stack with min() function, which will return the smallest number in the stack.

It should support push, pop and min operation all in O(1) cost.

Example

push(1)
pop()   // return 1
push(2)
push(3)
min()   // return 2
push(1)
min()   // return 1

Solution:

这道题如果正常的想法是设置一个全局变量，不停的纪录最小值的，但是在pop()后，如果被pop掉的是最小值，那么需要找到次小值，这里需要需要个辅助的数组去实现，首先解题的核心就是在于，构造一个一一对应的数组，比如堆栈中的第i个元素，在数组中则可以表示，数组中i个元素的最小值，这样可以很容易的在Pop的时候同步弹出，在Push的时候同步压入。

class MinStack(object):
    def __init__(self):
        self.stack = []
        self.minstack = [] 
    def push(self, number):
        self.stack.append(number)
        if len(self.minstack) > 0 : 
            self.minstack.append(min(number, self.minstack[-1]))
        else:
            self.minstack.append(number)
    def pop(self):
        if len(self.stack) > 0:
            self.minstack.pop()
            return self.stack.pop()
        return -1
    def min(self):
        return self.minstack[-1]