155.md

155. Min Stack

Description

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

Thinking Process

1. Use s1 to store the actual stack, s2 to store the min stack such that the corresponding position in s2 always stores the minimal values before that position.

public class MinStack {
    Stack<Integer> s1;
    Stack<Integer> s2;
    
    /** initialize your data structure here. */
    public MinStack() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }
    
    public void push(int x) {
        if(s1.empty() || x < s2.peek()){
            s2.push(x);
        }else{
            s2.push(s2.peek());
        }
        s1.push(x);
    }
    
    public void pop() {
        s1.pop();
        s2.pop();
    }
    
    public int top() {
        return s1.peek();
    }
    
    public int getMin() {
        return s2.peek();
    }
}

Complexity

1. Time complexity for each operation is O(1)
2. Space complexity is O(n)