剑指 Offer 59. 队列的最大值
大家好，我是程序员吴师兄，欢迎来到 图解剑指 Offer 结构化专栏，在这个专栏里我将和大家一起学习如何用结构化的思维来思考、解题、写代码，希望能帮助你即使在面试的时候紧张也能做对。
AlgoMooc 算法慕课网，每道题目都有动画和图片，致力于帮助每个程序员通过算法面试！
今天分享的题目来源于 LeetCode 上的剑指 Offer 系列**面试题 59. 队列的最大值 **。
题目汇总链接：https://www.algomooc.com/jianzhioffer
一、题目描述
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -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 <= push_back,pop_front,max_value的总操作数 <= 10000
- 1 <= value <= 10^5
二、题目解析
我们依旧用 四步分析法 进行结构化的分析。
- 模拟：模拟题目的运行。
- 规律：尝试总结出题目的一般规律和特点。
- 匹配：找到符合这些特点的数据结构与算法。
- 边界：考虑特殊情况。
1、模拟
这道题目和 用两个栈实现队列 是相似的，先来翻译一下示例一。
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
这个表示每一次操作的集合函数数组
[[],[1],[2],[],[],[]]
这个表示每一次操作后对应的参数的集合数组
题目要求我们查找最大值 max_value() 的时间复杂度达到 O(1) 级别，借助一个队列肯定是实现不了的，因为需要遍历整个队列才能获取到最大值。
在 用两个栈实现队列 一文中我们也说过，要想压缩时间得增大空间，即 “空间换时间” ，所以需要再构建一个队列。
为了保证第二个队列可以做到 O(1) 的级别拿到最大值，那么必须是它的队首始终是最大值，也就是说我们需要维护一个递减队列用来保存队列中 所有递减的元素 。
1、Max_queue
首先初始化，返回 null。
2、push_back
参数为 1，此时，两个队列为空，所以 1 入队 queue，同时 1 也入队 deque，返回 null。
3、push_back
参数为 2，此时 queue 和 deque 都有元素了，首先将 2 入队 queue，然后把双端队列 deque 中比 2 小的元素出队，以保持 deque 非单调递减，再把元素 2 入队 deque。
4、max_value
直接返回 deque 的队首元素就行。
5、pop_front
把 queue 的队首元素抛出就行，由于此时抛出的队首元素和 deque 不相等，所以deque 不需要执行任何操作。
5、max_value
直接返回 deque 的队首元素就行。
6、pop_front
为了更好的理解，我们再增加一组 pop_front 操作。
首先，把 queue 的队首元素抛出，由于此时抛出的队首元素和 deque 相等，所以deque 也需要抛出队首元素。
2、规律
每次操作都需要维护好deque，确保它保存队列中 所有递减的元素 。
3、匹配
- 队列
- 双端队列
4、边界
- 普通队列为空
- 双端队列为空
- 双端队列的队首元素和普通队列的队首元素不相等
三、动画描述
此处内容需要权限查看
会员免费查看四、图片描述
五、参考代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
class MaxQueue {
// 构建一个普通队列
Queue<Integer> queue;
// 构建双端队列
Deque<Integer> deque;
public MaxQueue() {
// 初始化
queue = new LinkedList<>();
deque = new LinkedList<>();
}
public int max_value() {
// 如果双端队列为空，返回 -1
if (deque.isEmpty()){
return -1;
}else{
// 否则返回双端队列的队首元素
return deque.peekFirst();
}
}
public void push_back(int value) {
// 普通队列直接添加元素
queue.add(value);
// 找出双端队列中那些少于当前元素值的元素
while(!deque.isEmpty() && deque.peekLast() < value){
deque.removeLast();
}
// 双端队列在尾部添加元素
deque.addLast(value);
}
public int pop_front() {
// 如果普通队列为空，返回 -1
if(queue.isEmpty()) {
return -1;
}
// 如果普通队列的队首元素和双端队列的队首元素相等，那么双端队列也需要移除队首元素
if(queue.peek().equals(deque.peekFirst())){
deque.removeFirst();
}
// 返回普通队列的队首元素就行了
return queue.remove();
}
}
六、复杂度分析
时间复杂度
时间复杂度为 O(1)。
空间复杂度
空间复杂度为 O(N)。
七、相关标签
- 队列
- 双端队列
