03.02. Min Stack

Description

How would you design a stack which, in addition to push and pop, has a function min which returns the minimum element? Push, pop and min should all operate in 0(1) time.

Example:


MinStack minStack = new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.getMin();   --> return -3.

minStack.pop();

minStack.top();      --> return 0.

minStack.getMin();   --> return -2.

Solutions

Solution 1: Double Stack

We use two stacks to implement this, where stk1 is used to store data, and stk2 is used to store the current minimum value in the stack. Initially, stk2 stores a very large value.

When we push an element x into the stack, we push x into stk1, and push min(x, stk2[-1]) into stk2.
When we pop an element from the stack, we pop the top elements of both stk1 and stk2.
When we want to get the top element in the current stack, we just need to return the top element of stk1.
When we want to get the minimum value in the current stack, we just need to return the top element of stk2.

For each operation, the time complexity is $O(1)$, and the space complexity is $O(n)$.

Python3JavaC++GoTypeScriptRustC#Swift

class MinStack:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.s = []
        self.mins = [inf]

    def push(self, val: int) -> None:
        self.s.append(val)
        self.mins.append(min(self.mins[-1], val))

    def pop(self) -> None:
        self.s.pop()
        self.mins.pop()

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

    def getMin(self) -> int:
        return self.mins[-1]


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()