Min Stack

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.

1 class MinStack { 2         List
        
          stack = new ArrayList
         
          (); 3     int top = -1; 4     int min = Integer.MAX_VALUE; 5  6     public void push(int x) { 7         top++; 8         stack.add(x); 9         if(min > x){10             min = x;11         12         }13             14     }15 16     public void pop() {17 18         int element = stack.remove(top--);19         if(element == min)20         {            21                 updateMin();            22                 23         }24     }25 26     public int top() {27         int result = stack.get(top);28       29         return result;30     }31 32     public int getMin() {33         34         return this.min;35     }36     public void updateMin(){37         if(top == -1)38         {39             min = Integer.MAX_VALUE;        40             return;41         }42         min = stack.get(0);43         for(int i = 1; i <= top; i++){44             if(min > stack.get(i))45                 min = stack.get(i);46         }47     }48 }