Min Stack: Using Two Stacks to Update MinValue

First Thoughts: class member variable that keeps track of the minimum value will be useful. getMin() can then simply return that class variable. Later, thought that using two stacks can help keep order (because if minimum value popped - or removed - need to update value, and if value pushed intermittently (not pushed one after another) it can disturb stack ordering -> need to first load all original stack elements and then add new value to be pushed. Every time a newcomer is pushed, check if its value is smaller than min.

My Solution:

class MinStack {
    
    Stack<Integer> stack;
    Stack<Integer> sub;
    int min;
    
    public MinStack() {
        stack = new Stack<>();
        sub = new Stack<>();
        min = Integer.MAX_VALUE;
    }
    
    public void push(int val) {
        if (val<min) min = val;
        stack.push(val);
    }
    
    public void pop() {
        int popped = stack.pop();
        updateMin(popped);
    }
    
    public int top() {
        return stack.peek();
    }
    
    private void updateMin(int popped) {
        if (popped!=min) return;
        min = Integer.MAX_VALUE;
        while (!stack.isEmpty()) {
            if (stack.peek()<min) min = stack.peek();
            sub.push(stack.peek());
            stack.pop();
        }
        while (!sub.isEmpty()) {
            stack.push(sub.peek());
            sub.pop();
        }
    }
    
    public int getMin() {
        return min;
    }
}

Catch Point:

• using two stacks to update minimum value (when minimum is popped) can be used to to update current minValue (move to sub temporarily, while checking individual values)

• important to differentiate between object stack (MinStack) and data structure stack (which is already defined in Java) -> remember, we're not editing the Java documentation of the stack structure

• 스택의 최소값은 유지되는데, 만약 pop된게 그 최소값이면 문제가 생기는 것 -> 이런 case를 pop할때마다 체크해주고 만약 진짜 맞다면 handle해줘야한다 (그 새로운 요소들 중에 또 최소값으로 업데이트)