首页 > 代码库 > 设计一个栈,除了pop与push方法,还支持Min方法,可返回栈元素中的最小值,push、pop、min三个方法的时间复杂度必须是O(1)
设计一个栈,除了pop与push方法,还支持Min方法,可返回栈元素中的最小值,push、pop、min三个方法的时间复杂度必须是O(1)
1 /* 2 * 设计一个栈,除了pop与push方法,还支持Min方法,可返回栈元素中的最小值, 3 * push、pop、min三个方法的时间复杂度必须是O(1) 4 * 一种解法是在Stack类里添加一个Int型的minValue,当minValue出栈时,我们会搜索整个栈 5 * 找出最新的最小值,但是却不符合操作时间为O(1)的要求 6 * 如有: 7 * push(4)//最小值:4 8 * push(5)//最小值:4 9 * push(3)//最小值:310 * push(1)//最小值:111 * pop() //最小值312 * 由以上例子,只要记下每种状态的最小值,我们就能很容易找出最小值。13 * 每个节点记录当前最小值,只要找到Min,直接查看栈顶元素就能找到最小值14 * 在这个程序中,利用例外的栈来记录这些Min15 * 16 * */17 18 import java.util.Stack;19 20 public class StackMin extends Stack<Integer> {21 22 Stack<Integer> s;23 public StackMin()24 {25 s=new Stack<Integer>();26 }27 public int min()28 {29 if(s.isEmpty())30 return Integer.MAX_VALUE;31 else 32 return s.peek();33 }34 public void push(int value)35 {36 if(value<=min()) //比较当前值与最小值,如果当前值比最小值小,就把当前值进栈37 s.push(value);38 super.push(value);39 }40 public Integer pop()41 {42 int value=http://www.mamicode.com/super.pop();43 if(value=http://www.mamicode.com/=min()) //如果当前值出栈,且是最小值,应把在保存最小值栈的最小值弹出44 {45 s.pop();46 }47 return value;48 }49 public static void main(String[] args) {50 // TODO Auto-generated method stub51 StackMin stack = new StackMin();52 System.out.println("当前最小值:"+stack.min());53 stack.push(5);54 stack.push(6);55 stack.push(3);56 stack.push(7);57 System.out.println("当前最小值:"+stack.min());58 stack.pop();59 stack.pop();60 System.out.println("当前最小值:"+stack.min());61 62 }63 64 }
设计一个栈,除了pop与push方法,还支持Min方法,可返回栈元素中的最小值,push、pop、min三个方法的时间复杂度必须是O(1)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。