【剑指offer：队列的最大值】使用双端队列来实现辅助队列
题目描述；请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数 max_value、push_back 和 pop_front 的均摊时间复杂度都是 O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1。
解法：辅助队列
使用两个队列，一个队列 queue 用于存放所有元素，另一个辅助队列 dequeue 用来存放当前 queue 中的最大值。
push 操作：
- 将元素放入 queue 中
- 检查元素是否大于 dequeue 队尾元素，如果大于，那么队尾元素出队；直到不再满足大于条件
pop 操作：
- 如果 queue 的队首元素等于 dequeue 的队首元素，那么 dequeue 队首元素需要出队
- queue 队首元素需要出队
题目要求复杂度控制在$O(1)$，所以必须使用双端队列来做辅助队列。因为 push 操作中，需要频繁对辅助队列的队尾元素进行移动操作。
代码实现如下：
// ac地址：https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/
// 原文地址：https://xxoo521.com/2020-03-28-max-queue/
var MaxQueue = function() {
this.queue = [];
this.dequeue = [];
};
/**
* @return {number}
*/
MaxQueue.prototype.max_value = function() {
return this.dequeue.length ? this.dequeue[0] : -1;
};
/**
* @param {number} value
* @return {void}
*/
MaxQueue.prototype.push_back = function(value) {
this.queue.push(value);
while (
this.dequeue.length &&
value > this.dequeue[this.dequeue.length - 1]
) {
this.dequeue.pop();
}
this.dequeue.push(value);
};
/**
* @return {number}
*/
MaxQueue.prototype.pop_front = function() {
if (!this.dequeue.length) {
return -1;
}
if (this.queue[0] === this.dequeue[0]) {
this.dequeue.shift();
}
return this.queue.shift();
};
/**
* Your MaxQueue object will be instantiated and called as such:
* var obj = new MaxQueue()
* var param_1 = obj.max_value()
* obj.push_back(value)
* var param_3 = obj.pop_front()
*/本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-03-28，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
