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.


class MinStack {
    
    private LinkedList<Node> stack = new LinkedList<>();
    
        
    /*     value, min
    
           -3, -3 
            0, -2
           -2, -2  
    */
        
    /** initialize your data structure here. */
    public MinStack() {
        
    }
    
    public void push(int x) {
        Node node;
        if (stack.isEmpty()) {
            node = new Node(x, x);
        } else {
            int min = Math.min(x, stack.peekFirst().min);
            node = new Node(x, min);
        }
        
        stack.push(node);
        
        System.out.printf("val %d min %d\n", node.value, node.min);
        
        
    }
    
    public void pop() {
        Node pop = stack.pop();
       System.out.printf("pop val %d min %d\n", pop.value, pop.min);
      
    }
    
    public int top() {
        return stack.peekFirst().value;
    }
    
    public int getMin() {
        Node first = stack.peekFirst();
        System.out.printf("getMin val %d min %d\n", first.value, first.min);
        return first.min;
    }
    
    class Node {
        
        Node(int value, int min) {
            this.value= value;
            this.min = min;
        }
        int value;
        int min;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */