Sharing my 279ms Java implementation


  • 2
    H

    I was just a little surprised at how quickly this ran, compared to the average.

    It ended up running in 279ms, which is right around average C++ territory.

    Thought you guys might be interested.

    class MinStack {
        class Item {
            Item next;
            Item nextSmallest;
            int value;
        }
        
        Item top;
        Item minimum;
            
        public void push(int x) {
            Item item = new Item();
            item.value = x;
            
            if (minimum == null) {
                minimum = item;
            } else if (x < minimum.value) {
                item.nextSmallest = minimum;
                minimum = item;
            }
            
            if (top != null) {
                item.next = top;
            }
            
            top = item;
        }
    
        public void pop() {
            if (top == minimum) {
                minimum = minimum.nextSmallest;
            }
            top = top.next;
        }
    
        public int top() {
            return top.value;
        }
    
        public int getMin() {
            return minimum.value;
        }
    }
    

    It seems like lots of people are using Stack<Integer>, but I thought there would be some memory/speed overhead using that, so I cooked up my own. Hope that's not against any rules.

    Reults:
    Graph


Log in to reply
 

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