思路
方法：维护一个单调的双端队列
1 class MaxQueue {
2 private:
3 queue<int> A;
4 deque<int> B;
5 public:
6 MaxQueue() {
7
8 }
9
10 int max_value() {
11 if(B.empty())
12 return -1;
13 return B.front();
14 }
15
16 void push_back(int value) {
17 A.push(value);
18 while(!B.empty() && value > B.back()) {
19 B.pop_back();
20 }
21 B.push_back(value);
22 }
23
24 int pop_front() {
25 if(A.empty()) {
26 return -1;
27 } else {
28 int tmp = A.front();
29 A.pop();
30 if(tmp == B.front())
31 B.pop_front();
32
33 return tmp;
34 }
35
36 }
37 };
38
39 /**
40 * Your MaxQueue object will be instantiated and called as such:
41 * MaxQueue* obj = new MaxQueue();
42 * int param_1 = obj->max_value();
43 * obj->push_back(value);
44 * int param_3 = obj->pop_front();
45 */