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     
 3     Stack<Integer>stack=new Stack<Integer>();
 4     
 5     Stack<Integer>min_stack=new Stack<Integer>();
 6     
 7     public void push(int x) {
 8         if(min_stack.isEmpty()||x<=min_stack.peek()){
 9             min_stack.push(x);
10         }
11         stack.push(x);
12     }
13 
14     public void pop() {
15         if(stack.peek().equals(min_stack.peek())){
16             min_stack.pop();
17         }
18         stack.pop();
19     }
20 
21     public int top() {
22         return stack.peek();
23     }
24 
25     public int getMin() {
26         return min_stack.peek();
27     }
28 }

用一个min_stack来记录当前最小值，以空间换时间的思想。