空间换时间----设计包含min函数的栈

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

凡事都按照题目来：这里的要求只有一个，就是时间复杂度是1，既然这样，那么我们可以把空间复杂度变成n来换取时间。。。霍霍

难点：在出栈的时候也要知道最小的元素是什么，所以必须记录每个阶段的最小元素的位置

思路：需要一个辅助栈。每次push一个新元素的时候，同时将最小元素的位置。push到辅助栈中；每次pop一个元素出栈的时候，同时pop辅助栈。

Class Stack{
  List<Integer> list = new ArrayList<Integer>();
  List<Integer> minList = new ArrayList<Integer>();
 
   public Integer pop(){
         minList.remove(minList.length);
         return list.remove(list.length);
   }

  public Integer getMin(){
       return list.get(minList.get(minList.length));
  }

  public Integer push(Integer i ){
       if(minList.length==0){
            minList.add(0);
            list.add(i);
       }else{
            Integer lastMinIndex = minList.get(minList.length);
            Integer lastMin = list.get(lastMinIndex);
            Integer minIndex = lastMin<i ? lastMinIndex : list.length+1;
            list.add(i);
            minList.add(minIndex);
      }
      
  }


}