欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

LintCode 12.带最小值操作的栈(两种方法实现)

程序员文章站 2022-03-21 19:34:02
题目描述 实现一个带有取最小值min方法的栈,min方法将返回当前栈中的最小值。 你实现的栈将支持push,pop 和 min 操作,所有操作要求都在O(1)时间内完成。 样例 如下操作:push(1),pop(),push(2),push(3),min(), push(1),min() 返回 1, ......

题目描述

实现一个带有取最小值min方法的栈,min方法将返回当前栈中的最小值。

你实现的栈将支持pushpop 和 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() 操作上做了一点改变,每次压栈时,若当前元素 <= 辅助栈栈顶元素时,则将当前元素压入栈,否则,继续压入辅助栈栈顶元素;

 

实现代码:

LintCode 12.带最小值操作的栈(两种方法实现)
 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 }
View Code

 

手动推导一遍样例(方法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() 操作时,只有在栈顶元素与当前栈出栈元素相同时才出栈。

 

实现代码:

LintCode 12.带最小值操作的栈(两种方法实现)
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;
    }
}
View Code

 

总结:方法1与方法2在LintCode上均提交成功,运行时间分别为 2042ms 和 2088ms .

直接使用Stack类实现栈,理解简单易上手,重点掌握其 push()、pop()、peek()等方法;而使用LinkedLIst类来实现栈,这里只是为了加强LinkedList的练习,

重点掌握其 addFirst()、getFirst()、removeFirst() 等方法;同时还可以用ArrayList类来实现栈。