如何获取最小值的栈

    现在需要实现一个栈，这个栈除了可以进行普通的push、pop操作以外，还可以进行getMin的操作，getMin方法被调用后，会返回当前栈的最小值。假设栈里面寸的都是int整数。

    可以申请一个辅助栈，辅助栈中保存最小值。辅助栈存储每次push的最小值，pop的时候两栈同步pop。这样一来所有操作的时间都是O(1)，空间是O(n)。

package com.mc.dao;
import java.util.ArrayList;
import java.util.List;


public class MinStack {
	private List<Integer> data = new ArrayList<Integer>();
	private List<Integer> mins = new ArrayList<Integer>();

	public void push(int num) {
		data.add(num);
		if (mins.size() == 0) {
			// 初始化mins
			mins.add(num);
		} else {
			// 辅助栈mins每次push当时最小值
			int min = getMin();
			if (num >= min) {
				mins.add(min);
			} else {
				mins.add(num);
			}
		}
	}

	public int pop() {
		// 栈空，异常，返回-1
		if (data.size() == 0) {
			return -1;
		}
		// pop时两栈同步pop
		mins.remove(mins.size() - 1);
		return data.remove(data.size() - 1);
	}

	public int getMin() {
		// 栈空，异常，返回-1
		if (mins.size() == 0) {
			return -1;
		}
		// 返回mins栈顶元素
		return mins.get(mins.size() - 1);
	}
}

    这个代码异常处理这块是定一个异常的返回值，这里定-1。
    但是会有点小问题，当栈内为空的时候，返回-1，但是如果用户push过-1，那么返回-1的时候，是用户push进来的值，还是栈为空，就不得而知了。
    可以用一个包装类Integer来定义返回值，如果是空，就代表栈为空就行了。它和int的区别就是它多了一个null，正好用来返回异常情况。
    但是这个栈的使用者，在pop的时候，并不知道可能返回null，如果不做判断，后面的代码可能抛出空指针。
    解决方法是抛出异常，这样使用者可以在异常捕获中获得异常信息。最关键的是，显式抛出异常，如果使用者不捕获，那么编译就会报错，这样就把错误暴露在编译阶段。

如果按照上面的算法，依次入栈2, 1, 2, 3, 4, 5, 6，辅助栈里的情况会是这样：2, 1, 1, 1, 1, 1, 1。这样的话，辅助栈后面都是1，并且大量重复，这块可以优化一下。
    可以在push的时候判断一下，如果比最小值还大，就不加入辅助栈。pop的时候，如果不是最小值，辅助栈就不出栈。这样一来，辅助栈就不会有大量重复元素了。
但是如果来了一个和最小值相等的数，要不要进辅助栈呢？
    也是要进的，不然最小值出栈后，下一个最小值就不对了。如果相等元素不进辅助栈，那么当其被pop的时候可能出错。
    如果入栈顺序是2, 1, 1, 1, 1, 1, 1，辅助栈中还是一堆1，所以这块还可以优化。
    将辅助栈里寸的值改为索引。
    辅助栈中改寸最小值在data数组中的索引。这样一来，当push了与最小值相同元素的时候，就不需要动辅助栈了。而pop的时候，pop出的元素的索引如果不是辅助栈栈顶元素，辅助栈也不出栈。同时，获取最小值的时候，需要拿到辅助栈栈顶元素作为索引，再去data数组中找到相应的数作为最小值。

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

public class MinStack {
	private List<Integer> data = new ArrayList<Integer>();
	private List<Integer> mins = new ArrayList<Integer>();

	public void push(int num) throws Exception {
		data.add(num);
		if (mins.size() == 0) {
			// 初始化mins
			mins.add(0);
		} else {
			// 辅助栈mins push最小值的索引
			int min = getMin();
			if (num < min) {
				mins.add(data.size() - 1);
			}
		}
	}

	public int pop() throws Exception {
		// 栈空，抛出异常
		if (data.size() == 0) {
			throw new Exception("栈为空");
		}
		// pop时先获取索引
		int popIndex = data.size() - 1;
		// 获取mins栈顶元素，它是最小值索引
		int minIndex = mins.get(mins.size() - 1);
		// 如果pop出去的索引就是最小值索引，mins才出栈
		if (popIndex == minIndex) {
			mins.remove(mins.size() - 1);
		}
		return data.remove(data.size() - 1);
	}

	public int getMin() throws Exception {
		// 栈空，抛出异常
		if (data.size() == 0) {
			throw new Exception("栈为空");
		}
		// 获取mins栈顶元素，它是最小值索引
		int minIndex = mins.get(mins.size() - 1);
		return data.get(minIndex);
	}
}