首页 > 代码库 > 设计一个栈,除了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)