题目
实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作.
要求
1.pop、push、getMin操作的时间复杂度都是O(1).
2.设计的栈类型可以使用现成的栈结构.
解题思路
在解决问题时，两种方案其实都是利用两个栈来实现，一个栈用来保存当前栈中的元素，其功能是一个正常的栈，将这个栈称为stackData；另一个栈用来保存每一步的最小值，这个栈称为stackMin。具体实现方式有两种.两种方案的其他方法均相同，只是压入数据和出栈的规则不同.
目录
初始化
第一种设计方案
压入数据
弹出数据
第一种方案完整代码
第二种设计方案
压入数据
弹出数据
第二种方案完整代码
总结
初始化
在获取当前栈中最小元素时，两种方案其实都是访问stackMin中的栈顶元素，且代码一样，因此直接将该方法初始化写出，后续代码仅描述两种方案的不同之处.
两种方案的初始化以及获取最小元素的方法一致，均为如下代码：
public class MinStack {
private Stack stackData;//保存当前栈中的元素
private Stack stackMin;//保存每一步的最小值
public MinStack() {
stackData = new Stack<>();
stackMin = new Stack<>();
}
public int getMin() {
if(this.stackMin.isEmpty()) {
throw new RuntimeException("栈为空，无法操作");
}
return this.stackMin.peek();
}
}
第一种设计方案
压入数据
假设当前数据为newNum，先将其压入stackData，然后判断stackMin是否为空：
1.如果为空，则newNum也压入stackMin中；
2.如果不为空，则比较newNum和stackMin的栈顶元素哪个更小：
①如果newNum较小或两者相等，则newNum也压入stackMin中；
②如果stackMin中栈顶元素较小，则stackMin中不压入任何内容.
例如要将3、4、5、1、2、1依次入栈，则根据上述压入数据方案，当所有元素入栈后，两个栈分别如下图所示：
具体代码：
public void push(int newNum) {
if(this.stackMin.isEmpty()) {
this.stackMin.push(newNum);
} else if(newNum <= this.getMin()) {
this.stackMin.push(newNum);
}
this.stackData.push(newNum);
}
弹出数据
先在stackData中弹出栈顶元素，记为value。然后比较当前stackMin的栈顶元素和value哪一个更小。根据压入规则，可以知道stackMin中的元素从栈底到栈顶是逐渐变小的，stackMin栈顶的元素即为当前所寻找的stackData栈中的最小值。
当value等于stackMin的栈顶元素时，stackMin弹出栈顶元素；当value大于stackMin的栈顶元素时，stackMin不弹出栈顶元素，返回value.
具体代码实现：
public int pop() {
if(this.stackData.isEmpty()) {
throw new RuntimeException("栈为空");
}
int value = this.stackData.pop();
if(value == this.getMin()) {
this.stackMin.pop();
}
return value;
}
第一种方案完整代码
import java.util.Stack;
public class MinStack {
private Stack stackData;
private Stack stackMin;
public MinStack() {
stackData = new Stack<>();
stackMin = new Stack<>();
}
//入栈操作
public void push(int newNum) {
if(this.stackMin.isEmpty()) {
this.stackMin.push(newNum);
} else if(newNum <= this.getMin()) {
this.stackMin.push(newNum);
}
this.stackData.push(newNum);
}
//删除栈顶元素
public int pop() {
if(this.stackData.isEmpty()) {
throw new RuntimeException("栈为空");
}
int value = this.stackData.pop();
if(value == this.getMin()) {
this.stackMin.pop();
}
return value;
}
//获取堆栈中最小元素
public int getMin() {
if(this.stackMin.isEmpty()) {
throw new RuntimeException("栈为空，无法操作");
}
return this.stackMin.peek();
}
}
第二种设计方案
压入数据
假设当前数据为newNum，先将其压入stackData，然后判断stackMin是否为空：
如果为空，则newNum也压入stackMin中，如果不为空，则比较newNum和stackMin的栈顶元素中哪一个更小：
①如果newNum更小或者两者相等，则将newNum也压入stackMin中；
②如果stackMin中栈顶元素小，则把stackMin的栈顶元素重复压入stackMin中，即在栈顶元素上再压入一个栈顶元素.
例如要将3、4、5、1、2、1依次入栈，则根据上述压入数据方案，当所有元素入栈后，两个栈分别如下图所示：
具体代码实现：
//入栈操作
public void push(int newNum) {
if(this.stackMin.isEmpty()) {
this.stackMin.push(newNum);
} else if(newNum < this.getMin()) {
this.stackMin.push(newNum);
} else {
int val = this.stackMin.peek();
this.stackMin.push(val);
}
this.stackData.push(newNum);
}
弹出数据
在stackData中弹出数据，弹出的数据即为value，并将stackMin栈顶的元素弹出，返回value即可
具体代码实现：
//删除栈顶元素
public int pop() {
if(this.stackData.isEmpty()) {
throw new RuntimeException("栈为空");
}
this.stackMin.pop();
return this.stackData.pop();
}
第二种方案完整代码
import java.util.Stack;
public class MinStack {
private Stack stackData;
private Stack stackMin;
public MinStack() {
stackData = new Stack<>();
stackMin = new Stack<>();
}
//入栈操作
public void push(int newNum) {
if(this.stackMin.isEmpty()) {
this.stackMin.push(newNum);
} else if(newNum < this.getMin()) {
this.stackMin.push(newNum);
} else {
int val = this.stackMin.peek();
this.stackMin.push(val);
}
this.stackData.push(newNum);
}
//删除栈顶元素
public int pop() {
if(this.stackData.isEmpty()) {
throw new RuntimeException("栈为空");
}
this.stackMin.pop();
return this.stackData.pop();
}
//获取堆栈中最小元素
public int getMin() {
if(this.stackMin.isEmpty()) {
throw new RuntimeException("栈为空，无法操作");
}
return this.stackMin.peek();
}
}
总结
两种方案都是利用两个栈实现，利用stackMin来保存stackData每一步的最小值。
其共同点时所有操作的时间复杂度都为O(1)、空间复杂度都为O(N)。
其区别为：
方案一中stackMin压入数据时相比方案二节省空间，但是弹出时费时间；
方案二中stackMin压入时相比方案一稍费空间，但弹出时节省时间.
