My ONE stack solution without any API - JAVA


  • 0
    K
    class MinStack {
    
        class DoubleyLinkedList{
            int val;
            DoubleyLinkedList next;
            DoubleyLinkedList prev;
            public DoubleyLinkedList(int val){
                this.val = val;
                next = null;
                prev = null;
            }
        } 
        DoubleyLinkedList head;
        DoubleyLinkedList tail;
        int min;
        /** initialize your data structure here. */
        public MinStack() {
            head = new DoubleyLinkedList(-1);
            tail = new DoubleyLinkedList(-1);
            min = Integer.MAX_VALUE;
            head.next = tail;
            tail.prev = head;
        }
        
        public void push(int x) {
            if (x <= min){
                DoubleyLinkedList cur = new DoubleyLinkedList(min);
                cur.prev = head;
                cur.next = head.next;
                head.next = cur;
                cur.next.prev = cur;
                min = x;
            }
            DoubleyLinkedList cur = new DoubleyLinkedList(x);
            cur.prev = head;
            cur.next = head.next;
            head.next = cur;
            cur.next.prev = cur;
        }
        
        public void pop() {
            DoubleyLinkedList peek = head.next;
            head.next = head.next.next;
            head.next.prev = head;
            if (peek.val == min){
                DoubleyLinkedList nextPeek = head.next;
                head.next = head.next.next;
                head.next.prev = head;
                min = nextPeek.val;
            }
        }
        
        public int top() {
            if (head.next == tail){
                return -1;
            }
            else {
                return head.next.val;
            }
        }
        
        public int getMin() {
            if (head.next == tail){
                return -1;
            }
            else {
                return min;
            }
        }
    }
    
    
    

Log in to reply
 

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