LintCode 12.带最小值操作的栈(两种方法实现)
题目描述
实现一个带有取最小值min方法的栈,min方法将返回当前栈中的最小值。
你实现的栈将支持push,pop 和 min 操作,所有操作要求都在O(1)时间内完成。
样例
如下操作:push(1),pop(),push(2),push(3),min(), push(1),min() 返回 1,2,1
先审题,返回值为1,2,1,分别是 pop(),min(),min() 这三个操作返回的值;在一般栈结构的基础上实现min方法来返回当前栈中的最小值,
我们可以增加一个辅助栈结构,用来记录当前栈的最小值。
手动推导一遍样例(方法1)
操作 |
当前栈:datastack |
辅助栈:minstack |
返回值 |
push(1) |
1 |
1 |
|
pop() |
空 |
空 |
1 |
push(2) |
2 |
2 |
|
push(3) |
2,3 |
2,2 |
|
min() |
2,3 |
2,2 |
2 |
push(1) |
2,3,1 |
2,2,1 |
|
min() |
2,3,1 |
2,2,1 |
1 |
从上表的推导过程来看,当前栈的 push(),pop()操作与一般栈无区别,新添加的 min() 操作每次返回的是当前栈中的最小值元素,即辅助栈的栈顶元素;
而增加的辅助栈在 push() 操作上做了一点改变,每次压栈时,若当前元素 <= 辅助栈栈顶元素时,则将当前元素压入栈,否则,继续压入辅助栈栈顶元素;
实现代码:
1 import java.util.Stack; 2 3 public class MinStack { 4 public static void main(String[] args) { 5 MinStack stack = new MinStack(); 6 stack.push(1); 7 stack.pop(); 8 stack.push(2); 9 stack.push(3); 10 stack.min(); 11 stack.push(1); 12 stack.min(); 13 14 } 15 16 Stack<Integer> datastack = new Stack<Integer>(); 17 Stack<Integer> minstack = new Stack<Integer>(); 18 19 /*当前栈压栈,1)最小值栈为空时,将该元素记录为最小值栈栈顶元素;2)最小值栈非空时,将该元素与最小值栈栈顶元素比较,谁小谁入栈;*/ 20 public void push(int num) { 21 int top; 22 datastack.push(num); 23 if(!minstack.empty()) 24 top = minstack.peek(); 25 else 26 top = num; 27 28 if(num > top) 29 minstack.push(top); 30 else 31 minstack.push(num); 32 33 //System.out.println("push"+num+"时当前栈的栈顶元素为:"+datastack.peek()); 34 //System.out.println("push"+num+"时最小值栈的栈顶元素为:"+minstack.peek()); 35 36 } 37 /*返回当前栈栈顶元素,当前栈与最小值栈同时出栈;*/ 38 public int pop() { 39 if(!datastack.isEmpty()) { 40 int data = datastack.peek(); 41 datastack.pop(); 42 minstack.pop(); 43 //return data; 44 System.out.println("当前栈中的最小值为:"+ data); 45 } 46 return 0; 47 } 48 /*判断当前栈是否非空,返回当前栈中的最小值,即最小值栈的栈顶元素;*/ 49 public int min() { 50 if(!datastack.isEmpty()) { 51 //return minstack.peek(); 52 System.out.println("当前栈中的最小值为:"+minstack.peek()); 53 } 54 return 0; 55 } 56 }
手动推导一遍样例(方法2)
操作 |
当前栈:datastack |
辅助栈:minstack |
返回值 |
push(1) |
1 |
1 |
|
pop() |
空 |
空 |
1 |
push(2) |
2 |
2 |
|
push(3) |
2,3 |
2 |
|
min() |
2,3 |
2 |
2 |
push(1) |
2,3,1 |
2,1 |
|
min() |
2,3,1 |
2,1 |
1 |
方法2与方法1区别在于,第一点:方法2使用LinkedList数据结构来实现栈,而不是如方法1中直接使用Stack来实现栈;
第二点:方法2的辅助栈的 push() 操作只在栈为空或者当前元素 < 辅助栈栈顶元素时,才压栈;pop() 操作时,只有在栈顶元素与当前栈出栈元素相同时才出栈。
实现代码:
import java.util.LinkedList; public class MinStack { public static void main(String[] args) { MinStack stack = new MinStack(); stack.push(1); stack.pop(); stack.push(2); stack.push(3); stack.min(); stack.push(1); stack.min(); } LinkedList datastack = new LinkedList<Integer>(); LinkedList minstack = new LinkedList<Integer>(); /* 当前栈压栈,最小值栈为空时或者该元素比最小值栈栈顶元素小时压栈 */ public void push(int num) { datastack.addFirst(num); if(minstack.isEmpty()||num <= (int)minstack.getFirst()) { minstack.addFirst(num); } } /* 判断当前栈非空,则出栈,若出栈元素与最小值栈栈顶元素相同,则也须出栈 */ public int pop() { int data; if(!datastack.isEmpty()) { data = (int)datastack.removeFirst(); if(data == (int)minstack.getFirst()) { minstack.removeFirst(); } //return data; System.out.println(data); } return 0; } /* 返回最小值栈的栈定元素即所求的最小元素 */ public int min() { if(!datastack.isEmpty()) { return (int)minstack.getFirst(); //System.out.println((int)minstack.getFirst()); } return 0; } }
总结:方法1与方法2在LintCode上均提交成功,运行时间分别为 2042ms 和 2088ms .
直接使用Stack类实现栈,理解简单易上手,重点掌握其 push()、pop()、peek()等方法;而使用LinkedLIst类来实现栈,这里只是为了加强LinkedList的练习,
重点掌握其 addFirst()、getFirst()、removeFirst() 等方法;同时还可以用ArrayList类来实现栈。
上一篇: Python中的默认参数实例分析