Min Stack

Question

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.

Thoughts

用两个stack

• 一个像正常的stack一样
• 另一个keep track of the minimum
  • 只有当 新push的number <= 现在的min时，才会push到这个stack上
  • 只有当 pop的number == 现在的min, 才会从这个stack上pop

Test Cases 和 注意点

• 当一开始为空时的push
• 每一个push与现有min相等时也要push到stack2上

Solution

class MinStack(object):

    def __init__(self):
        # do some intialize if necessary
        self.stack1 = []
        self.minStack = []

    def push(self, number):
        # write yout code here
        self.stack1.append(number)
        if self.minStack:
            curMin = self.minStack[-1]
            if number <= curMin:
                self.minStack.append(number)
        else:
            self.minStack.append(number)

    def pop(self):
        # pop and return the top item in stack
        c = self.stack1.pop()
        curMin = self.minStack[-1]
        if c == curMin:
            self.minStack.pop()
        return c

    def min(self):
        # return the minimum number in stack
        return self.minStack[-1]