贡献一个Facebook题目

jimmyzzxhlh 发表于 2016-6-23 06:46
Min Queue似乎要比Min Stack难
http://stackoverflow.com/questions/12054415/get-min-max-in-o1-time-fro ...

1.         class MinQueue {
   
2.                
   
3.                 Queue<Integer> queue;
   
4.                 Deque<Integer> deque;
   
5.                
   
6.                 public MinQueue() {
   
7.                         queue = new LinkedList<Integer>();
   
8.                         deque = new ArrayDeque<Integer>();
   
9.                 }
   
10.                
    
11.                 public void offer(int x) {
    
12.                         if (queue.size() == 0) {
    
13.                                 queue.offer(x);
    
14.                                
    
15.                                 deque.offer(x);
    
16.                         }
    
17.                         else {
    
18.                                 queue.offer(x);
    
19.                                 for (Iterator<Integer> it = deque.descendingIterator(); it.hasNext();) {
    
20.                                         if (it.next() > x) {
    
21.                                                 it.remove();
    
22.                                         }
    
23.                                 }
    
24.                                 deque.offer(x);
    
25.                         }
    
26.                 }
    
27.                
    
28.                 public int remove() {
    
29.                         if (queue.size() == 0) return -1;
    
30.                         int val = 0;
    
31.                         if (queue.peek() == deque.peek()) {
    
32.                                 val = queue.remove();
    
33.                                 deque.remove();
    
34.                         }
    
35.                         else {
    
36.                                 val = queue.remove();
    
37.                         }
    
38.                         return val;
    
39.                 }
    
40.                
    
41.                 public int getMin() {
    
42.                         return deque.getFirst();
    
43.                 }
    
44.                
    
45.         }

复制代码

jimmyzzxhlh 发表于 2016-6-23 06:54

多谢代码，请问为啥要用deque，两个queue感觉也可以解决问题？

zhaoshiwen520 发表于 2016-6-23 08:44
多谢代码，请问为啥要用deque，两个queue感觉也可以解决问题？

我那个做法里需要反过来遍历Deque删除所有deque里比当前的x大的元素，queue不能反过来遍历

jimmyzzxhlh 发表于 2016-6-23 08:49
我那个做法里需要反过来遍历Deque删除所有deque里比当前的x大的元素，queue不能反过来遍历

哦，明白了，queue不能反向便利

239. Sliding Window Maximum

用两个minstack实现minqueue也行，平均也是O1

祝楼主好运！

jimmyzzxhlh 发表于 2016-6-23 08:49
我那个做法里需要反过来遍历Deque删除所有deque里比当前的x大的元素，queue不能反过来遍历

一样的思想 用两个stack就可以解决了

hello2pig 发表于 2016-9-14 21:46
一样的思想 用两个stack就可以解决了

请问两个stack怎么做？谢谢

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies