题目:定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数,在该栈中,调用min,push及pop的时间复杂度都是O(1).
这道题在《剑指Offer》中出现过(第21题),在很多公司的面试也频频出现。解决方案如下:
1,利用空间换时间:
建立一个数据栈用于保存进栈的数据,建立一个辅助栈用于保存数据栈各个时期的最小数据。
2,进栈:往数据栈中push一个数据x,如果辅助栈为空或者其栈顶元素大于x,则将x压入辅助栈。(辅助栈栈顶始终保存数据栈的最小数据)
3,出栈:数据栈pop一个数据,辅助栈也pop一个数据
4,获取min函数:辅助栈的栈顶元素就是数据栈中的最小数据。
代码实现如下
package suanfa.datastruct; import java.util.Stack; public class StackWithMin { /* * dataStack:数据栈 * assistStack:辅助栈 */ private Stack<Integer> dataStack; private Stack<Integer> assistStack; /* * 构造器 */ public StackWithMin(){ dataStack = new Stack<Integer>(); assistStack = new Stack<Integer>(); } public void push(Integer value){ dataStack.push(value); pushMin(value); } /* * 往辅助栈中压入数据 * 若待压入数据x大于辅助栈的栈顶元素y,则压入y * 若待压入数据x小于辅助栈的栈顶元素y,则压入x */ public void pushMin(Integer newValue){ if(assistStack.empty()){ assistStack.push(newValue); return; } Integer peekValue = assistStack.peek(); if(newValue <= peekValue){ assistStack.push(newValue); }else{ assistStack.push(peekValue); } } /* * 出栈:数据栈和辅助栈同时出栈。 */ public void pop(){ dataStack.pop(); assistStack.pop(); } /* * 获取栈中最小元素 */ public Integer getMin(){ System.out.print("栈中最小元素为:"); System.out.println(assistStack.pop()); return assistStack.pop(); } /* * 输出栈中所有元素,输出顺序为栈低--->栈顶 */ public void printStack(){ System.out.println("输出栈中元素:"); System.out.print("<<栈底"); for (Integer value : dataStack){ System.out.print(value + ","); } System.out.println("栈顶>>"); } /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub StackWithMin stackWithMin = new StackWithMin(); stackWithMin.push(5); stackWithMin.push(2); stackWithMin.push(3); stackWithMin.printStack(); stackWithMin.getMin(); stackWithMin.push(1); stackWithMin.push(4); stackWithMin.pop(); stackWithMin.printStack(); stackWithMin.getMin(); } }