本系列導(dǎo)航：劍指offer（第二版）java實現(xiàn)導(dǎo)航帖
面試題30：包含min函數(shù)的棧
題目要求：
定義棧的數(shù)據(jù)結(jié)構(gòu)瘩将，請在該類型中實現(xiàn)一個能夠得到棧的最小元素的min函數(shù)。要求在該棧中雌续，調(diào)用min，push及pop的時間復(fù)雜度都是o(1)。
解題思路：
期望獲知當(dāng)前棧的最小值瞻离，最直接的方法是全部彈出求最小值碎浇，然后再全部壓入临谱。這種方式時間消耗較大。另一種思路南捂，可以用空間換時間：自己實現(xiàn)一個棧吴裤，棧中有記錄數(shù)據(jù)的數(shù)據(jù)棧，同時也有記錄最小值的min棧溺健，本帖就是采用的此方法麦牺。記得曾經(jīng)看過一個更巧妙地方法，用一個變量來記錄最小值鞭缭，壓入與彈出都會因一定的規(guī)則修改該變量剖膳，思路比較精奇，可遇不可求岭辣，有興趣的可以去搜搜看,比如吱晒。
package chapter4;
import java.util.Stack;
/**
* Created by ryder on 2017/7/16.
* 包含min函數(shù)的棧
*/
public class P165_StackWithMin {
public static void main(String[] args){
StackWithMin<Integer> stack = new StackWithMin<>();
stack.push(3);
stack.push(4);
stack.push(2);
stack.push(1);
System.out.println(stack.min());
stack.pop();
System.out.println(stack.min());
stack.pop();
System.out.println(stack.min());
stack.pop();
System.out.println(stack.min());
stack.pop();
System.out.println(stack.min());
}
}
class StackWithMin<T extends Comparable>{
private Stack<T> stackData = new Stack<>();
private Stack<T> stackMin = new Stack<>();
public void push(T data){
stackData.push(data);
if(stackMin.isEmpty())
stackMin.push(data);
else{
T temp = stackMin.peek();
if(temp.compareTo(data)<0)
stackMin.push(temp);
else
stackMin.push(data);
}
}
public T pop(){
if(stackData.isEmpty())
return null;
stackMin.pop();
return stackData.pop();
}
public T min(){
if(stackMin.isEmpty())
return null;
return stackMin.peek();
}
}
運行結(jié)果
1
2
3
3
null
