剑指 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)。
七、相关标签
- 队列
- 双端队列