面试题30：包含min函数的栈
题目要求：
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。要求在该栈中，调用min，push及pop的时间复杂度都是o(1)。
解题思路：
期望获知当前栈的最小值，最直接的方法是全部弹出求最小值，然后再全部压入。这种方式时间消耗较大。另一种思路，可以用空间换时间：自己实现一个栈，栈中有记录数据的数据栈，同时也有记录最小值的min栈，本帖就是采用的此方法。记得曾经看过一个更巧妙地方法，用一个变量来记录最小值，压入与弹出都会因一定的规则修改该变量，思路比较精奇，可遇不可求，有兴趣的可以去搜搜看,比如。
package chapter4;
import java.util.Stack;
/**
* Created by ryder on 2017/7/16.
* 包含min函数的栈
*/
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();
}
}
运行结果
1
2
3
3
null
