《剑指offer》面试题21 包含min函数的栈 Java版

（min函数的作用是返回栈内最小值）

首先这个栈要具有普通栈所具有的push()和pop()方法，那么内部一定包含一个Stack。至于还要能实现min函数，而且还是在O(1)时间复杂度内，我们不得不考虑用额外的空间。

如果直接使用一个int变量存储当前的最小值，我们的确可以获得最小值，但是当栈pop()了以后，我们无法获得次小值。我们需要一个数据结构来动态保存每个时刻的最小值，每当push()和pop()的时候，同样更新这个数据结构，而且时间复杂度也是O(1)，那么看来需要额外O(n)的空间了。可以选择栈或者一个链表（实质上当作栈使用）。我们使用一个辅助栈来实现，该栈和主栈的大小相同，栈顶存放的是当前栈内的最小值。

书中方法：

public class StackContainingMinFunc{
    Stack<Integer> origin = new Stack<Integer>();
    Stack<Integer> sup = new Stack<Integer>();
    public void push(int item){
        origin.push(item);
        if(sup.isEmpty()){
            sup.push(item);
        }else sup.push(sup.peek()<item ? sup.peek() : item);
    }

    public int pop(){
        assert(origin.size()>0 && sup.size()>0);
        sup.pop();
        return origin.pop();
    }

    public int min(){
        assert(origin.size()>0 && sup.size()>0);
        return sup.peek();
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        StackContainingMinFunc s = new StackContainingMinFunc();
        s.push(5);
        System.out.println(s.min());
        s.push(4);
        System.out.println(s.min());
        s.push(3);
        System.out.println(s.min());
        s.push(6);
        System.out.println(s.min());
        s.pop();
        System.out.println(s.min());
        s.pop();
        System.out.println(s.min());
        s.pop();
        System.out.println(s.min());
    }

}