Min Stack

Problem: Min Stack

We can use two stacks to implement a min stack, one for elements and one for min elements. When we want to push a number, we check whether it's a new min by checking top of min stack. If it is, we push it into min stack at the same time when we push it into the normal stack. When we want to pop the top element, we check whether it's current min. If so, we pop it from min stack too.

Code in Python:

class MinStack(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.min_stack = []

    def push(self, x):
        """
        :type x: int
        :rtype: nothing
        """
        self.stack.append(x)
        if not self.min_stack:
            self.min_stack.append(x)
        elif self.min_stack[-1] >= x:
            self.min_stack.append(x)

    def pop(self):
        """
        :rtype: nothing
        """
        if self.min_stack[-1] == self.stack[-1]:
            self.min_stack.pop()
        self.stack.pop()

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

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