Ac solution code


  • 1

    The basic idea is using two stacks: one stack is for all elements, the other one is for minimum elements. The trick in this solution is:

    1. Push x into minStack: Only when 1) minStack is empty; 2) x is smaller than the top of minStack;
    2. Pop element from minStack: Only when the top of stack equals the top of minStack.

    By this trick, only minimum elements will be pushed to minStack for the corresponding elements in the stack, as the following:

    public class MinStack {
    	Stack<Integer> minStack = null;
    	Stack<Integer> stack = null;
    	
    	public MinStack() {
    		minStack = new Stack<Integer>();
    		stack = new Stack<Integer>();		
    	}
    	
        public void push(int x) {
        	if (minStack.isEmpty() || x <= minStack.peek())// Push x into minStack: Only when 1) minStack is empty; 2) x is smaller  than the top of minStack
        		minStack.push(x);
        	stack.push(x);    	    	     
        }
        
        public void pop() {
            if (stack.peek().equals(minStack.peek()))//Pop from minStack: Only when the top of stack equals the top of minStack 
            	minStack.pop();
            stack.pop();
        }
    
        public int top() {
            return stack.peek(); 
        }
    
        public int getMin() {
        	return minStack.peek();
        }
    }

Log in to reply
 

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