8ms clean Java Solution using ArrayLists


  • 1
    R

    Use two Lists - one for 'stack' and another for minimum values until now.

    In push, check if top element in 'minStack' is greater than or equal to new integer, if yes then add that to both stacks.

    In pop, check if top of 'stack' list is same as top of 'minStack', if yes then remove top element from both stacks.

    In average case, 'minStack' size tend to be very small as compared to 'stack'.

    class MinStack {
    
        private List<Integer> stack;
        private List<Integer> minStack;
    
        public MinStack(){
            stack = new ArrayList<Integer>();
            minStack = new ArrayList<Integer>(); 
        }
        
        public void push(int x) {
            stack.add(x);
            if(minStack.isEmpty()){
                minStack.add(x);
            }
            else if(minStack.get(minStack.size()-1)>=x){
                minStack.add(x);
            }
        }
    
        public void pop() {
            if(this.top() == minStack.get(minStack.size()-1)){
                minStack.remove(minStack.size()-1);
            }
            stack.remove(stack.size()-1);
        }
    
        public int top() {
            return stack.get(stack.size()-1);
        }
    
        public int getMin() {
            return minStack.get(minStack.size()-1);
        }
    }

  • 1

    public class MinStack {

    public static void main(String[] args) {
    	MinStack s = new MinStack();
    	s.push(10);
    	s.push(20);
    	s.push(45);
    	s.push(1);
    	//System.out.println(s.top);
    	s.pop();
    	//System.out.println(s.top);
    	//System.out.println(s.getMin());
    }
    
    Node top;
    public void push(int x) {
    	
    
    	if (top == null) {
    		top = new Node();
    		top.value = x;
    		top.min = x;
    
    	} else {
    		Node temp = new Node();
    		temp.value = x;
    		if (top.min > x) {
    			temp.min = x;
    		} else {
    			temp.min = top.min;
    		}
    
    		top.next = temp;
    		temp.prev = top;
    		top = temp;
    
    	}
    	//System.out.println(x + "is pushed!");
    }
    
    public void pop() {
    	if (top != null) {
    		if (top.prev == null) {
    			//System.out.println(top.value + "is popped!");
    			top = null;
    
    			return;
    		} else {
    			Node temp = top.prev;
    			//System.out.println(top.value + "is popped!");
    			temp.next = null;
    			top.prev = null;
    			top = temp;
    			return;
    		}
    	} else {
    		//System.out.println("empty stack!");
    		return;
    	}
    
    }
    
    public int top() {
    	if (top != null) {
    		//System.out.println(top.value + "is on top!");
    
    		return top.value;
    	} else
    		throw new NullPointerException();
    }
    
    public int getMin() {
    	if (top != null) {
    		//System.out.println(top.min + "is on min!");
    		return top.min;
    	} else
    		throw new NullPointerException();
    
    }
    

    }

    class Node {
    int value;
    int min;
    Node next;
    Node prev;

    }


  • 0
    B

    I did basically the same solution as you, however I would consider using a Deque (specifically ArrayDeque) instead of ArrayList. They are very similar, but the deque class provides many many useful methods such as peek() and pop() and push() and even has better runtimes than arraylist for many common operations:

    http://stackoverflow.com/questions/6129805/what-is-the-fastest-java-collection-with-the-basic-functionality-of-a-queue


  • 1
    G

    Hi,I've had a question. why it turns to be wrong when I simply change nothing but this.top() to stack.get(stack.size() - 1)?


  • 0
    G

    @gilbertwang0159
    I meet the exactly same problem.


  • 0
    H

    @gilbertwang0159 @Gary2954 because here the stack is PRIVATE!


Log in to reply
 

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