微软算法100题02 设计包含min函数的栈

要求：
1. 定义栈的数据结构，要求添加一个 min函数，能够得到栈的最小元素
2. 要求函数 min、push 以及 pop 的时间复杂度都是 O(1)

思路: 构建一个辅助栈, 只有当前入栈的数据小于该辅助栈的栈顶元素时，才将其push到辅助栈, 保证辅助栈的栈顶元素总为最小，当出栈时，如果出栈元素大于辅助栈栈顶元素，则该元素必然不在辅助栈中，因为辅助栈保留了原始栈的入栈顺序(只按大到小存储舍弃了一些元素), 该较大元素在入栈时就已经被辅助栈过滤掉了，如果出栈元素小于或等于辅助栈栈顶元素，则辅助栈也进行pop操作

 1 package com.rui.microsoft;
 2 
 3 import java.util.Stack;
 4 
 5 public class Test02_MinStack {
 6 
 7     public static void main(String[] args) {
 8         MyStack myStack = new MyStack();
 9         myStack.push(5);
10         myStack.push(3);
11         myStack.push(1);
12         myStack.push(6);
13         
14         System.out.println(myStack.min());
15         
16         myStack.pop();
17         System.out.println(myStack.min());
18         
19         myStack.pop();
20         System.out.println(myStack.min());
21         
22     }
23     
24     static class MyStack{
25         private Stack<Integer> stack = new Stack<Integer>();
26         private Stack<Integer> minStack = new Stack<Integer>();
27         
28         public void push(int i){
29             stack.push(i);
30             
31             if(minStack.isEmpty()){
32                 minStack.push(i);
33             }else{
34                 int min = minStack.peek();
35                 //minStack only push item smaller than its top item
36                 //minStack只入栈比其栈顶元素小的元素
37                 if(i < min){
38                     minStack.push(i);
39                 }
40             }
41         }
42         
43         public Integer pop(){
44             Integer i = stack.pop();
45             //when pop an item from original stack
46             //we need to process the minStack also
47             //if the item popped from original stack is larger than minStack's top item
48             //it means this item should not exist in minStack
49             if(i <= minStack.peek()){
50                 minStack.pop();
51             }
52             return i;
53         }
54         
55         public Integer min(){
56             return minStack.peek();
57         }
58     }
59 }