270ms solution in Java using LinkedList. However, one question remains: what's the minimum value if the stack is empty?


  • 0
    A
    class MinStack {
        class Node{
            int val;
            Node next;
            
            public Node(int v)
            {
                val = v;
                next = null;
            }
            
        }
        
        Node top;
        int min;
        public MinStack()
        {
            top = null;
            min = Integer.MAX_VALUE;
        }
        
        
        public void push(int x) {
            // if stack is empty
            if(top == null) 
            {
                Node temp = new Node(x);
                top = temp;
            }
            else
            {
                Node temp = new Node(x);
                temp.next = top;
                top = temp;
            }
            
            if(x < min)
            {
                min = x;
            }
            
        }
    
        public void pop() {
            if(top.val == min)
            {
                min = Integer.MAX_VALUE;
                Node walker = top.next;
                while (walker!= null)
                {
                    min = walker.val < min? walker.val: min;
                    walker=walker.next;
                }
            }
            
            top = top.next;
            
        }
    
        public int top() {
            return top.val;
            
        }
    
        public int getMin() {
            return min;
            
        }
    }
    

    basically using linkedlist, and update the variable "min" everytime the new value is smaller than it..
    after popping the node, if the top node of the stack has the same value with min, it will scan the whole stack again to search the new minimum value.

    Only one thing that still makes me confused..
    what if the stack is empty? what is its minimum value? since integer cannot be null.. is it -1?


Log in to reply
 

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