当前位置：首页 > news >正文

[CareerCup][Google Interview] 实现一个具有get_min的Queue

news 来源：原创 2024/4/15 21:37:17

Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.

http://www.careercup.com/question?id=7263132给出了很精彩的解答。

主要的思想是维护一个min_queue，保存当前队列最小值，当新加入一个元素时，min_queue遵照这样的规则

从min_queue的尾部开始和新加入元素（key）比较，当min_queue.back() > key时，弹出back()，直到back()<= key，或者min_queue为空。

当要返回min时，return min_queue.front()

而pop()时，比较queue.front() == min_queue.front()，相等则min_queue.pop_front()

这里，最关键的思想是后来的key和min_queue从后往前比较，能够保证min_queue是一个非降序列，这样就能维护一个当前队列的最小值序列。

分摊下来，每个操作O(1)

 1 #include <iostream>
 2 #include <deque>
 3 using namespace std;
 4 
 5 class Queue
 6 {
 7 private:
 8     deque<int> q;
 9     deque<int> minq;
10 
11 public:
12     void push(int key)
13     {
14         q.push_back(key);
15         while(!minq.empty())
16         {
17             if (minq.back() > key)
18                 minq.pop_back();
19             else
20                 break;
21         }
22         minq.push_back(key);
23     }
24 
25     int pop()
26     {
27         int element = q.front();
28         q.pop_front();
29         if (element == minq.front())
30             minq.pop_front();
31         return element;
32     }
33 
34     int get_min()
35     {
36         return minq.front();
37     }
38 };
39 
40 int main()
41 {
42     Queue q;
43 
44     q.push(12);
45     cout << q.get_min() << endl;
46 
47     q.push(4);
48     cout << q.get_min() << endl;
49 
50     q.push(8);
51     cout << q.get_min() << endl;
52 
53     q.pop();
54     q.pop();
55     cout << q.get_min() << endl;
56 
57     q.push(7);
58     cout << q.get_min() << endl;
59 
60     q.pop();
61     cout << q.get_min() << endl;
62 
63     q.push(6);
64     q.push(6);
65     cout << q.get_min() << endl;
66 
67     q.pop();
68     cout << q.get_min() << endl;
69 }