问题

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的getMin和最大元素的getMax函数。在该栈中，调用getMin、getMax、push及pop的时间复杂度都是O(1).。

解题思路

用辅助栈记住每次入栈的当前最小值/最大值：在入栈时，往辅助栈中加入当前最小值/最大值；出栈时，辅组栈也出栈一个元素。最小值/最大值从辅助栈中获取栈顶元素。

基础代码实现

import java.util.ArrayList;
import java.util.EmptyStackException;
import java.util.List;

public class MyStack {

    private List<Integer> data = new ArrayList<Integer>(); //数据栈
    private List<Integer> min  = new ArrayList<Integer>();  //存放最小值的栈
    private List<Integer> max  = new ArrayList<Integer>();  //存放最大值的栈

    public void push(int num) {
        data.add(num);
        if (min.size() == 0) {
            //如果最小栈空，则初始化
            min.add(num);
            max.add(num);
        } else {
            if (num > getMin()) {
                min.add(min.get(min.size() - 1));
            } else {
                min.add(num);
            }
            if (num < getMax()) {
            	max.add(max.get(max.size() - 1));
            } else {
            	max.add(num);
            }
        }
    }

    public int pop() {
        if (data.size() == 0) {
        	throw new EmptyStackException();
        }
        min.remove(min.size() - 1);
        max.remove(max.size() - 1);
        return data.remove(data.size() - 1);
    }

    public int getMin() {
        if (data.size() == 0) {
        	throw new EmptyStackException();
        } else {
            return min.get(min.size() - 1);
        }
    }
    
    public int getMax() {
        if (data.size() == 0) {
        	throw new EmptyStackException();
        } else {
            return max.get(max.size() - 1);
        }
    }
}

改进分析

基础实现中有两点未考虑：

空间增大：如果入栈分别是2、1、2、3、4、5、6，辅助栈min里面会变成 2、1、1、1、1、1、1，而辅助栈max里面会变成2、2、2、3、4、5、6，辅助栈中会有大量重复数据。
未使用泛型，该栈的数据结构仅支持int类型数据。

改进1

入栈时，当数据大于辅助栈min top的值，则辅组栈min则不入栈，同样，当数据小于辅助栈max top的值，则辅组栈max则不入栈。
出栈时，当数据大于辅助栈min top的值，则辅组栈min则不出栈，同样，当数据小于辅助栈max top的值，则辅组栈max则不出栈。
修改后，代码push/pop如下：

    public void push(int num) {
        data.add(num);
        if (min.size() == 0) {
            //如果最小栈空，则初始化
            min.add(num);
            max.add(num);
        } else {
            if (num <= getMin()) {
                min.add(num);
            }
            if (num >= getMax()) {
            	max.add(num);
            }
        }
    }

    public int pop() {
        if (data.size() == 0) {
        	throw new EmptyStackException();
        }
        if (data.get(data.size() - 1) <= min.get(min.size() - 1)) {
        	min.remove(min.size() - 1);
        }
        if (data.get(data.size() - 1) >= max.get(max.size() - 1)) {
        	max.remove(max.size() - 1);
        }
        return data.remove(data.size() - 1);
    }