如何获取栈的最小值
1、基本方法：增加辅助栈，辅助栈里面存储每次存放的最小值。如图所示原理，
代码实现：
public class MinStack1 {
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的异常返回值，但是当栈内为空的时候，返回的是-1，如果用户push过-1，那么返回的-1到底是用户push进来的值，还是栈为空，这个是个矛盾点。
2.辅助栈数据冗余的问题：
2、正确的解锁姿势（最优）：用辅助栈记录存储数据最小值的下标。
mins 栈中改存最小值在 data 数组中的索引。这样一来，当 push 了与最小值相同元素的时候，就不需要动 mins 栈了。
而 pop 的时候，pop 出的元素的索引如果不是 mins 栈顶元素，mins 也不出栈。
同时，获取最小值的时候，需要拿到 mins 栈顶元素作为索引，再去 data 数组中找到相应的数作为最小值。
代码实现：
public class MinStack2 {
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);
}
}
参考资料：公众号互联网侦察