Java 122ms solution with one LikedList, beats 68%, easy to understand


  • 1
    R

    First I tried to travel through the whole stack each time when the getMin() method was called, but it cost too much time and exceeded the time limit. Then I figure out the we can store the min value and the current value in an object, and the stack stores the new objects, like this:

    class Item{
        int val;
        Item min;
    }
    

    And every time we push a new element, compare it with the min value stored in the last element and update the min value if necessary. The whole code is :

    public class MinStack {
    
        /** initialize your data structure here. */
        LinkedList<Item> item;
    	int size;
    	
        public MinStack() {
        	item = new LinkedList<>();
        	size = 0;
        }
        
        public void push(int x) {
        	Item newItem = new Item();
        	newItem.val = x;
            if (isEmpty()) {
            	newItem.min = newItem;
            } else {
            	int lastMinVal = item.getLast().min.val;
            	if (x < lastMinVal)
            		newItem.min = newItem;
            	else
            		newItem.min = item.getLast().min;
            }
            item.addLast(newItem);
            size++;
        }
        
        public void pop() {
            if (!isEmpty()) {
            	item.removeLast();
            	size--;
            }
            	
        }
        
        public int top() {
            if (!isEmpty())
            	return item.getLast().val;
            else
            	return -1;
        }
        
        public boolean isEmpty(){
        	return size == 0;
        }
        
        public int getMin() {
            return item.getLast().min.val;
        }
        
        class Item{
        	int val;
        	Item min;
        }
    }

Log in to reply
 

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