Min Stack

The stack can be implemented using LinkedList implementation. So the problem is how to track the minimum efficiently. One way to do it is to design a structure and store the minimum of all elements prior to head into the stack. Thus each node will also contain the information of the local minimum. The problem with this method is that there will be lots of duplicate data. For example, if I have a stack (0, 1, 2, 3, 4), the head is 4, with the minimum 0, every node stores 0, which is unnecessary and infeasible for very large stack.

So the question is, how can we do better?

One approach may be to use another List, or another stack to only track the local minimum. If the pushed node is smaller than the minimum of all existing nodes in the stack, push the node to the second stack. So for (0, 1, 2, 3, 4), we will have another list/stack only contains (0).

class MinStack {
    ListNode head;
    ListNode currMin;
    public MinStack() {
        head = null;
        currMin = null;
    }
    public MinStack(int val) {
        head = new ListNode(val);
        currMin = new ListNode(val);
    }
    
    public void push(int x) {
        if (head == null) {
            head = new ListNode(x);
            currMin = new ListNode(x);
        }
        else {
            ListNode node = new ListNode(x);
            node.next = head;
            head = node;
            //if there are two nodes with the same minimum value in the stack, 
            //if we delete the first one, or the one pushed in later, the minimum
            //of the stack is still the same value, thus we need to push the node
            //to the min stack as long as it equals the minimum
            if (x <= currMin.val) {
                //need to create a new node and push it
                //to the second list, 
                //otherwise the current node's next will points to next min
                //because we override it with the previous min
                ListNode tmp = node;
                tmp.next = currMin;
                currMin = tmp;
            }
        }
    }

    public void pop() {
        if (head == null)
            return;
        if (currMin.val == head.val) {
            currMin = currMin.next;
        }
        head = head.next;
    }

    public int top() {
        if (head == null)
            return -1;
        return head.val;
    }

    public int getMin() {
        if (head == null)
            return -1;
        return currMin.val;
    }
    private class ListNode{
        int val;
        ListNode next;
        public ListNode(int val) {
            this.val = val;
            next = null;
        }
    }
}