面试题59 - II. 队列的最大值

面试题59 - II. 队列的最大值

难度：$middle$

题目描述

请定义一个队列并实现函数 maxvaluemax_valuemaxv​alue 得到队列里的最大值，要求函数maxvaluemax_valuemaxv​alue、pushbackpush_backpushb​ack 和 popfrontpop_frontpopf​ront 的 均摊 时间复杂度都是O(1)。

若队列为空，popfrontpop_frontpopf​ront 和 maxvaluemax_valuemaxv​alue 需要返回 -1

示例 1：

输入: 
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]

示例 2：

输入: 
["MaxQueue","pop_front","max_value"]
[[],[],[]]
输出: [null,-1,-1]

限制：

• 1<=pushback,popfront,maxvalue的总操作数<=100001 <= push_back,pop_front,max_value的总操作数 <= 100001<=pushb​ack,popf​ront,maxv​alue的总操作数<=10000
• 1<=value<=1051 <= value <= 10^51<=value<=105

算法

(单调队列)

为了实现此递减列表，需要使用 双向队列 ，假设队列已经有若干元素：

• 当执行入队 push_back() 时： 若入队一个比队列某些元素更大的数字 x ，则为了保持此列表递减，需要将双向队列 尾部所有小于 x 的元素 弹出。
• 当执行出队 pop_front() 时： 若出队的元素是最大元素，则 双向队列 需要同时 将首元素出队 ，以保持队列和双向队列的元素一致性。

使用双向队列原因：维护递减列表需要元素队首弹出、队尾插入、队尾弹出操作皆为 O(1) 时间复杂度。

函数设计：

1. 初始化队列 queue ，双向队列 deque ；

2. 最大值 max_value() ：

   当双向队列 deque 为空，则返回 −1 ；
   否则，返回 deque 首元素；

3. 入队 push_back() ：
   将元素 value 入队 queue ；
   将双向队列中队尾 所有 小于 value 的元素弹出（以保持 deque 非单调递减），并将元素 value 入队 deque ；

4. 出队 pop_front() ：
   若队列 queue 为空，则直接返回 −1 ；
   否则，将 queue 首元素出队；
   若 deque 首元素和 queue 首元素 相等 ，则将 deque 首元素出队（以保持两队列 元素一致 ） ；

复杂度分析

• 时间复杂度：$O(1)$

• 空间复杂度 : $O(n)$

C++ 代码

class MaxQueue {
public:queue<int> q;deque<int> dq;MaxQueue() {}int max_value() {if (q.empty()) return -1;return dq.front();}void push_back(int value) {q.push(value);while (!dq.empty() && value > dq.back()) dq.pop_back();dq.push_back(value);}int pop_front() {if (q.empty()) return -1;int ans = q.front();q.pop();if (ans == dq.front()) dq.pop_front();return ans;}
};/*** 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();*/