Using Doubly linked list with one extra pointer (Java Solution) 269ms


  • 0
    S

    Use linked list as main body.

    Use an extra pointer to account for the current node.

    Run time is really fast.

    class MinStack {
        class Node{
            int val;
            Node next;
            Node pre; 
            Node last;// pointers to next minimun Node
            Node(int x){
                val = x;
                next = null;
                pre = null;
                last = null;
            }
        }
        
        Node head = new Node(0);
        Node tail = head;
        Node min = null;
        
        public void push(int x) {
            Node node = new Node(x);
            // set stack
            tail.next = node;
            node.pre = tail;
            tail = node;
            // set min
            if(min==null){
                min = node;
            }else{
                if(node.val < min.val){
                    node.last = min;
                    min = node;
                }else{
                    node.last = min;
                }
            }
        }
    
        public void pop() {
            if(tail==head){
                return;
            }else{
                min = tail.last;
                tail = tail.pre;
            }
        }
    
        public int top() {
            return tail.val;
        }
    
        public int getMin() {
            return min==null?0:min.val;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.