如何实现获取最小值的栈

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

1、先来一个时间复杂度很高的方法

解决1：可以用一个变量来保存最小值，在push的时更新这个最小值

定义一个变量min，保存最小值，在push的时候进行更新

问题是：如果最小值被pop出去了，该如何处理呐？

pop的时候将最小值4出栈了，谁是下一个最小值？

解决2：如果最小值被pop出去了，那就只能遍历栈内元素，再更新最小值了

pop的时候，如果最小值出栈，需要遍历data找到新的最小值。

所以这个方法的时间和空间复杂度是？

pop的时间复杂度是O(n)，其他操作的时间复杂度都是O(1)，空间复杂度是O(1)

2、时间复杂度很短的方法

解决1：用空间换时间，申请一个辅助栈，辅助栈中用来保存最小值。

辅助栈mins存储每次push当时的最小值，pop时两栈同步pop

这个方法的时间和空间复杂度是？

所有操作的时间复杂度是O(1)，空间复杂度是O(n)。

有缺陷的代码实现：

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进来的值，还是栈为空，这个是个矛盾点。

解决2：抛出异常，可以在异常捕获中获取异常信息，显示抛出异常，如果使用者不捕获，那么编译就会报错，这样就把错误暴露在编译阶段，如果不捕获异常，那连运行都运行不起来。

3、算法优化

第二步已经将算法优化到时间复杂度为O(1)，空间复杂度为O(n)了。还可以继续优化这个算法，使得空间还可以再小一点点。

按照算法，依次入栈是2，1，2，3，4，5，6，那么在辅助栈里会是什么样子的？

辅助栈中的后面全是1，并且大量重复，可以对此优化一下。

解决1：我可以在push的时候判断一下，如果比最小值还大，就不加入辅助栈。pop的时候，如果不是最小值，辅助栈就不出栈。这样一来，辅助栈就不会有大量重复元素了。

push的时候进行判断，如果数值比当前最小值大，就不动mins栈了，这样mins栈中，不会保存大量冗余的最小值。pop的时候同样进行判断，只有pop出的数，就是当前最小值的时候，才让mins出栈。

问题：如果进来一个和最小值相等的值，要不要进辅助栈？

和最小值相等的数也要进栈，不然最小值出栈后，下一个最小值就不对了。

如果push一个和最小值相等的元素，还是要入mins栈。不然当这个最小值pop出去的时候。data中还会有一个最小值元素，而mins中却已经没有最小值元素了。

如果入栈顺序是2，1，1，1，1，1，1，那么辅助栈里面还是一堆1，所以还是可以优化的。

可以将辅助栈里不存值，存索引，就可以解决这个问题了。

mins栈中改存最小值在data数组中的索引。这样一来，当push了与最小值相同元素的时候，就不需要动mins栈了。而pop的时候，pop出的元素的索引，如果不是mins栈顶元素，mins也不出栈。同时，获取最小值的时候，需要拿到mins栈顶元素作为索引，再去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);
    }

}