题目描述
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
Example1:
输入: ["MaxQueue","push_back","push_back","max_value","pop_front","max_value"] [[],[1],[2],[],[],[]] 输出: [null,null,null,2,1,2]
Example2:
输入: ["MaxQueue","pop_front","max_value"] [[],[],[]] 输出: [null,-1,-1]
限制
- 1 <= push_back,pop_front,max_value的总操作数 <= 10000
- 1 <= value <= 10^5
解题思路
- 借助双端队列
- 在插入的时候，从后面遍历这个双端队列，弹出比value值小的
- 因为比value小的，一定是比value先弹出的
class MaxQueue {
public:
MaxQueue() {
}
int max_value() {
if(d1.empty()){
return -1;
}
return d1.front();
}
void push_back(int value) {
q1.push(value);
// 借助双端队列
// 这里找到插入value的位置
// 不需要保留比value小的元素原因是
// 这些数字一定是比value更早弹出的
// 所以 只要value不弹出，这里面的最大的，一定是value前面的
while(!d1.empty() && d1.back() < value){
d1.pop_back();
}
d1.push_back(value);
}
int pop_front() {
if(q1.empty()){
return -1;
}
int x = q1.front();
q1.pop();
if(x == d1.front()){
d1.pop_front();
}
return x;
}
private:
queue<int> q1;
deque<int> d1;
};
/**
* Your MaxQueue object will be instantiated and called as such:
* MaxQueue* obj = new MaxQueue();
* int param_1 = obj->max_value();
* obj->push_back(value);
* int param_3 = obj->pop_front();
*/
