剑指offer 09.用两个栈实现队列——30.包含min函数的栈


题目描述:(栈和队列)

09——用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 );

 

解题思路:

 

1.栈无法去实现队列功能:栈底元素无法直接删除,需要将上方的所有元素出栈

2.使用双栈即可实现列表倒序及列表元素删除功能

 

 

对于这题我们可以直接使用两个函数,利用栈A用于加入队尾操作,栈B用于删除操作(将A元素倒序)

 

 1 class CQueue{
 2 
 3 LinkedList<Integer> A.B;
 4    public CQuere(){
 5       
 6     A = new LinkedList<Integer>();
 7     B = new LinkedList<Integer>();
 8       }
 9 //加入操作
10    public void appendTail(int value){
11            
12            A.addLast(value);
13 
14       }
15 
16    public int deleteHead(){
17 
18        if(!B.isEmpty())  return B.removeLast();
19        if(A.isEmpty())  return -1;
20        while(!A.isEmpty()){
21                     B.addLast(A.removeLast());
22                 }
23      return B.removeLast();
24       }
25 
26 }

 

 

 

30——定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。

 

 

解题思路:

由于普通栈的push()和pop()函数的复杂度为O(1) ;而获取栈的最小值min() 函数需要遍历整个栈,复杂度为O(N)

我们如果要降低复杂度的话,可以建立通过辅助栈实现

数据栈A:栈A用于储存所有元素,保证入栈的push函数,出栈的pop函数,及获取栈顶的top函数的正常逻辑

辅助栈B:栈B用来储存A中所有“非严格降序”的元素,栈A中的最小元素始终对应栈B的栈顶元素,所以min函数只要返回B的栈顶元素即可

 1 class MinStack{
 2 
 3 Stack<Integer> A,B;
 4 public MinStack(){
 5 
 6 A = new Stack<Integer>();
 7 B = new Stack<Integer>();
 8       }
 9 
10 public void push(int x){
11 A.add(x);
12 if(B.isEmpty() || B.peek() >= x){
13           B.add(x);
14              }
15        }
16 public void pop(){
17 
18    if(A.pop().equals(B.peek()){
19            B.pop();
20 }
21        }
22 public int top(){
23         return A.peek();
24       }
25 
26 public int min(){
27        return B.peek();
28       }
29 }

 

剑指offer 09.用两个栈实现队列——30.包含min函数的栈

上一篇:腾讯云从业者认证考试答案哪里有?证书作用有哪些?认证考试可以延期吗?


下一篇:039.程序流程结构-跳转语句-continue语句