题目：
实现一个特殊的栈，在实现栈的基本功能上，再实现返回栈中的最小元素
要求：
1. pop、push、getMin操作的时间复杂度都是O（1）
2. 设计的栈类型可以使用现成的栈
思路：
在设计的时候、我们使用两个栈、一个栈用来保存当前栈中的元素、其功能和一个正常的栈没有什么区别、这个栈记为stackData，另一个栈用来存当前的最小值、记为stackMin
第一种 设计方案
第一种设计流程图
(1)压入规则
① 如果stackMin为空直接压入newNum。
② 如果stackMin不为空，先是用getMin（）查看stackMin栈顶元素，newNum和栈顶元比较，newNum小于等于，压入newNum、否则不压入。
③ 不管是那一不都必须把newNum压入stackData。
（2）弹出规则
弹出stackData的栈顶元素value、和stackMin的栈顶元素比较，如果等于弹出stackMin栈顶元素
（3）查询
就是使用栈的peek()方法查询stackMin的栈顶元素
代码演示
public class StackMin1 {
private StackstackData;
private StackstackMin;
public StackMin1() {
this.stackData =new Stack<>();
this.stackMin =new Stack<>();
}
/**
* 进栈操作，如果栈中没有这直接加入两个栈，如果stackMin中有，newNum被stackMin的栈顶元素小则加入，
* 否则不加入，
*
* @param newMun
*/
public void push(int newMun) {
if (this.stackMin.isEmpty()) {
this.stackMin.push(newMun);
}else if (newMun <=this.getMin()) {
this.stackMin.push(newMun);
}
stackData.push(newMun);
}
/**
* 弹出方法
*
* @return
*/
public int pop() {
if (this.stackData.isEmpty()) {
throw new RuntimeException("你还没有添加数据");
}
int value =stackData.pop();
if (value ==this.getMin()) {
this.stackMin.pop();
}
return value;
}
/**
* 查看栈顶元素
*
* @return 返回栈顶元素
*/
public int getMin() {
if (this.stackMin.isEmpty()) {
throw new RuntimeException("没有数据");
}
// 查看存最小值的那个栈的栈顶元素
return this.stackMin.peek();
}
public static void main(String[] args) {
int[] arr = {3, 4, 5, 1, 2, 1};
StackMin1 stackMin1 =new StackMin1();
for (int i =0; i < arr.length; i++) {
stackMin1.push(arr[i]);
}
for (int i =0; i < arr.length; i++) {
System.out.println(stackMin1.getMin()+" " +stackMin1.pop() );
}
}
}
第二种 设计方案
第二种方案流程图
(1)压入规则
① 如果stackMin为空直接压入newNum。
② 如果stackMin不为空，先是用getMin（）查看stackMin栈顶元素，newNum和栈顶元比较，newNum小于等于，压入newNum、否则不压入。
③ 如果stackMin的栈顶元素较小，则在压入一遍
④ 不管是那一不都必须把newNum压入stackData。
（2）弹出规则
直接分别弹出stackMin和StackData即可
（3）查询
就是使用栈的peek()方法查询stackMin的栈顶元素
代码演示
class StackMin2 {
private StackstackMin;
private StackstackData;
public StackMin2() {
this.stackData =new Stack<>();
this.stackMin =new Stack<>();
}
public void push(int newNum) {
if (this.stackMin.isEmpty()) {
this.stackMin.push(newNum);
}else if (newNum
this.stackMin.push(newNum);
}else {
int min =this.getMin();
this.stackMin.push(min);
}
this.stackData.push(newNum);
}
public int pop() {
if (this.stackMin.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();
}
}
总结：
两种方案的时间复杂度和空间复杂度都分别是O(1)、O(n)，只是方法一：在压入的时候稍微省空间、但弹出的时候稍微费时间，方案二 在压入的时候稍微费空间、但弹出的时候稍微省时间。
文献：左程云著 《程序员代码面试指南IT名企算法与数据结构题目最优解》（第二版）
版权声明：此文版权归作者所有！
