package com.fishercoder.solutions;

import java.util.*;

/**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.
 Example:
 _155 minStack = new _155();
 minStack.push(-2);
 minStack.push(0);
 minStack.push(-3);
 minStack.getMin();   --> Returns -3.
 minStack.pop();
 minStack.top();      --> Returns 0.
 minStack.getMin();   --> Returns -2.
 */
public class _155 {
    
    private Stack<Integer> stack;
    private int min;

    /** initialize your data structure here. */
    public _155() {
        stack = new Stack();
        min = Integer.MAX_VALUE;
    }
    
    public void push(int x) {
        /**All the trick happens here, we push the second minimum number onto the stack before we push the newer one,
         * this way, when popping, we could always get the next minimum one in constant time.*/
        if(x <= min){
            stack.push(min);
            min = x;
        }
        stack.push(x);
    }
    
    public void pop() {
        if(min == stack.peek()){
            stack.pop();
            min = stack.pop();
        } else {
            stack.pop();
        }
        if(stack.isEmpty()) min = Integer.MAX_VALUE;
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return min;
    }

}

@@ -53,16 +53,38 @@
 .*;%0A%0A/**
+%0A * 155. Min Stack%0A * 
 Design a
@@ -174,16 +174,18 @@
  time.%0A%0A
+ *
  push(x)
@@ -215,16 +215,18 @@
  stack.%0A
+ *
  pop() -
@@ -268,16 +268,18 @@
  stack.%0A
+ *
  top() -
@@ -301,16 +301,18 @@
 lement.%0A
+ *
  getMin(
@@ -359,16 +359,19 @@
  stack.%0A
+%0A *
  Example
@@ -373,20 +373,26 @@
 ample:%0A 
-_155
+* MinStack
  minStac
@@ -403,16 +403,22 @@
 new 
-_155
+MinStack
 ();%0A
+ *
  min
@@ -433,16 +433,18 @@
 sh(-2);%0A
+ *
  minStac
@@ -454,16 +454,18 @@
 ush(0);%0A
+ *
  minStac
@@ -476,16 +476,18 @@
 sh(-3);%0A
+ *
  minStac
@@ -516,16 +516,18 @@
 rns -3.%0A
+ *
  minStac
@@ -535,16 +535,18 @@
 .pop();%0A
+ *
  minStac
@@ -574,16 +574,18 @@
 urns 0.%0A
+ *
  minStac
@@ -618,16 +618,17 @@
 -2.%0A */%0A
+%0A
 public c
@@ -639,21 +639,56 @@
  _155 %7B%0A
+%0A
     
-%0A
+public static class MinStack %7B%0A    
     priv
@@ -713,24 +713,28 @@
  stack;%0A    
+ 
+   
 private int 
@@ -743,18 +743,33 @@
 n;%0A%0A    
-/*
+    /**%0A         
 * initia
@@ -802,16 +802,25 @@
 ere.
+%0A        
  */%0A    
 publ
@@ -819,24 +819,36 @@
     
+   
+ 
 public 
-_155
+MinStack
 () %7B%0A
+    
     
@@ -876,24 +876,28 @@
 ();%0A        
+ 
+   
 min = Intege
@@ -905,39 +905,43 @@
 .MAX_VALUE;%0A    
+   
-%7D
+ %7D%0A
 %0A    
-%0A
     public void 
@@ -962,16 +962,20 @@
         
+  
+  
 /**All t
@@ -1085,16 +1085,20 @@
         
+    
 * this w
@@ -1184,18 +1184,23 @@
         
+    
 if
+ 
 (x %3C= mi
@@ -1201,16 +1201,17 @@
  %3C= min)
+ 
 %7B%0A      
@@ -1208,32 +1208,36 @@
 ) %7B%0A            
+    
 stack.push(min);
@@ -1245,24 +1245,28 @@
             
+    
 min = x;%0A   
@@ -1262,16 +1262,20 @@
 in = x;%0A
+    
         
@@ -1276,32 +1276,36 @@
       %7D%0A        
+    
 stack.push(x);%0A 
@@ -1303,31 +1303,35 @@
 ush(x);%0A    
+  
-%7D
+  %7D%0A
 %0A    
-%0A
     public v
@@ -1350,18 +1350,23 @@
         
+  
+  
 if
+ 
 (min == 
@@ -1378,16 +1378,17 @@
 .peek())
+ 
 %7B%0A      
@@ -1385,32 +1385,36 @@
 ) %7B%0A            
+  
+  
 stack.pop();%0A   
@@ -1402,32 +1402,36 @@
    stack.pop();%0A
+    
             min 
@@ -1453,16 +1453,20 @@
         
+    
 %7D else %7B
@@ -1466,16 +1466,20 @@
  else %7B%0A
+    
         
@@ -1487,32 +1487,36 @@
    stack.pop();%0A
+    
         %7D%0A      
@@ -1517,18 +1517,23 @@
         
+    
 if
+ 
 (stack.i
@@ -1567,31 +1567,35 @@
 _VALUE;%0A    
-%7D
+    %7D%0A
 %0A    
-%0A
     public i
@@ -1609,24 +1609,28 @@
 ) %7B%0A        
+ 
+   
 return stack
@@ -1646,15 +1646,19 @@
     
+   
-%7D
+ %7D%0A
 %0A    
-%0A
     
@@ -1683,24 +1683,28 @@
 ) %7B%0A        
+   
+ 
 return min;%0A
@@ -1703,16 +1703,26 @@
 rn min;%0A
+        %7D%0A
     %7D%0A%0A%7D

edit 155