剑指offer：包含min函数的栈
题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
要求以时间复杂度为O(1)来得到栈中的最小元素，那就要保证最小元素一直在栈顶，这样才可以随时弹出。如果在原本的栈中操作，这样就不能保证栈中最后进入的元素最先被弹出了，因此我们需要借助外部空间来进行操作。
如果我们定义一个变量min来表示最小元素，每当压入栈一个元素，都将这个元素和最小元素进行比较，如果比min下，就更新min为当前这个元素，min中存放的是当前栈中最小的元素，但是会有一个问题，如果栈中这个min对应的元素被弹出了，那此时min的值就不能表示新栈中的最小元素值了，因此不能用变量定义。
建立一个新的临时栈用来存储当前栈中的最小元素，每当入栈一个新的元素，都将这个元素和min栈中的元素进行比较，如果比它小，则将这个元素也压入min栈。这样min栈的顶部弹出的永远都是当前栈中最小的元素。
存入min栈的元素有两种方式，
方式1：
如果当前要压入栈的元素比min栈存储的最小值小，则将这个元素压入min栈，否则，将min栈中的最小值重新压入min栈。
方式2：
如果当前要压入栈的元素比min栈存储的最小值小，则将这个元素压入min栈，否则，min栈不做更新，不存入任何新数据。
对于数据栈，这操作都方式都是一样的，对于min栈，两种不同的操作方式，区别是：
对于方式1：每当新元素入栈，min栈也会同步增加min值，保持数据栈和辅助栈的长度是一致的，这样在pop的时候，对于数据栈和辅助栈，只需要同时pop就可以。
对于方式2：只有在新元素比min栈中的min小的时候才将它压入min栈，否则，min栈不进行任何操作，这样的话，在pop的时候就需要判断当前pop的值是否是min栈中栈顶的值，如果是，min栈也pop，否则，只对数据栈pop。
方式2 的优势是，数据栈新元素入栈和栈顶元素出栈时，min栈会少操作几步压入和弹出操作。缺点是，弹出需要做判断。
而方式1的弹出不用做任何判断，保持同步就行。
代码1：
package com.day01;
import java.util.Stack;
public class MinInStack {
/*思路：需要借助一个辅助栈来存放最小元素。
* 每次压入一个新元素进栈的时候，如果该元素比当前最小的元素还要小，则更新最小元素。
* 但是如果当前最小的元素被弹出了，怎么得到下一个最小的元素是一个问题，
* 因此只添加一个成员变量存放最小元素是不够的，即当最小元素被弹出时，我们希望能够的得到次小的元素。
* 因此在压入最小元素之前，我们要把次小的元素保存起来。因此可以借助一个辅助栈把每次的最小元素保存起来*/
Stack<Integer> data=new Stack<>();//存放元素栈
Stack<Integer> min=new Stack<>();//辅助栈，data栈中每次进入一个元素，min辅助栈就存放当前data栈中的最小元素
//data栈和min栈进入元素
public void push(int node){
data.push(node);
if(min.size()==0||node<min.peek()){
min.push(node);
}else{
min.push(min.peek());
}
}
//data栈和min栈中弹出元素
public void pop(){
if(data.size()>0&&min.size()>0){
data.pop();
min.pop();
}
}
//data栈的栈顶元素
public int top(){
if(data.size()>0){
return data.peek();
}
return 0;
}
//min栈的栈顶元素，栈顶元素为data栈中现有元素的最小元素
public int min(){
if(data.size()>0&&min.size()>0){
return min.peek();
}
return 0;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
MinInStack mis=new MinInStack();
mis.push(3);
mis.push(2);
mis.push(4);
mis.push(3);
System.out.println(mis.min());
}
}
代码2：
package com.day01;
import java.util.Stack;
public class MinInStack2 {
Stack<Integer> data=new Stack<>();
Stack<Integer> min=new Stack<>();
public void push(int node) {
data.push(node);
if(min.size()==0||node<min.peek()){
min.push(node);
}
}
public void pop() {
if(data.size()>0&&min.size()>0){
int peek=data.peek();
data.pop();
if(peek==min.peek()){
min.pop();
}
}
}
public int top() {
if(data.size()>0){
return data.peek();
}
return 0;
}
public int min() {
if(min.size()>0){
return min.peek();
}
return 0;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
MinInStack mis=new MinInStack();
mis.push(3);
mis.push(2);
mis.push(4);
mis.push(3);
System.out.println(mis.min());
}
}
参考：