155. Min Stack Leetcode Java

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

Solution:

An easy solution is maintain two stacks and one of them s1 is to store the normal elements the other one s2 stores the minimum elements so for. So whenever there is push, s1.push(x), s2.push(Math.Min(x,min)). For pop(), both two stacks will pop, and getMin() will be s2.peek().

An advanced solution is just push min to s2 when the min is changed which means the current x become the new min. When doing the pop(), we do the same thing, check if the popped element from s1 is the top element in s2, if yes, pop s2 as well. Eg. now we push the following elements: 3,4,2,5 in s2, we only needs to push 3,2. Because even when we pop 5 out of s1, it won't affect the minimum which is 2. But when we pop out 2 from s1, we have to pop out 2 from s2 as well, that because the minimum has been popped out, and the minimum becomes the 3, which is minimum of current s1(3,4).  This solution will save little spaces for the average case, but for worst case, they use same space.

     class MinStack {  
   Stack<Integer> st=new Stack<Integer>();  
   Stack<Integer> min=new Stack<Integer>();  
   public void push(int x) {  
     st.push(x);  
     if(min.isEmpty() || x<=min.peek()) min.push(x);  
   }  
   public void pop() {  
     int x=st.pop();  
     if(!min.isEmpty() && min.peek()==x) min.pop();  
   }  
   public int top() {  
     return st.peek();  
   }  
   public int getMin() {  
     return min.peek();  
   }  
 }