【java】剑指offer59-II_队列的最大值
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【java】剑指offer59-II_队列的最大值,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2441字,纯文字阅读大概需要4分钟。
内容图文
![【java】剑指offer59-II_队列的最大值](/upload/InfoBanner/zyjiaocheng/590/308011a7be5540fdb7cdcc18147b2e1d.jpg)
题目描述
请定义一个队列并实现函数 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
参考解题思路:双端队列,一个队列记录队列中入队、出队,双端队列维系目前队列中值的单调递减顺序,返回最大值
函数设计:
- 初始化队列 queue ,双向队列 deque ;
- 最大值 max_value() :
- 当双向队列 deque 为空,则返回?1 ;
- 否则,返回 deque 首元素;
- 入队 push_back() :
- 将元素 value 入队 queue ;
- 将双向队列中队尾 所有 小于 value 的元素弹出(以保持 deque 非单调递减),并将元素 value 入队 deque ;
- 出队 pop_front() :
- 若队列 queue 为空,则直接返回?1 ;
- 否则,将 queue 首元素出队;
- 若 deque 首元素和 queue 首元素 相等 ,则将 deque 首元素出队(以保持两队列 元素一致 ) ;
小tips:设计双向队列为 单调不增 的原因:若队列 queue 中存在两个 值相同的最大元素 ,此时 queue 和 deque 同时弹出一个最大元素,而 queue 中还有一个此最大元素;即采用单调递减将导致两队列中的元素不一致。
// 定义双端队列和队列
Deque<Integer> deque; // 双端队列维系队列元素递减规律
Queue<Integer> queue; // 队列用于压入弹出队首元素
public Offer59II() {
deque = new LinkedList<>();
queue = new LinkedList<>();
}
public int max_value() {
// 如果双端队列不为空则检索队首元素返回
if (!deque.isEmpty()) {
return deque.peekFirst();
}
return -1;
}
public void push_back(int value) {
queue.offer(value); // 队列追加元素
// 如果双端队列不为空且队尾元素小于新追加元素--则加入到队尾中
while (!deque.isEmpty() && value > deque.peekLast()) {
deque.pollLast(); // 删除双端队列队尾小于新追加值的原数值
}
deque.offerLast(value); // 双端队列追加新值
}
public int pop_front() {
if (!queue.isEmpty()) {
// 如果队首元素等于栈首元素则同时弹出栈首元素
// 这里用equals比较两个封装类,用==比较的地址会出错
if (deque.peekFirst().equals(queue.peek())) {
deque.pollFirst(); // 弹出队首元素
}
return queue.poll(); // 队列弹出队首元素
}
return -1;
}
复杂度分析:
时间复杂度 O(1): max_value(), push_back(), pop_front() 方法的均摊时间复杂度均为 O(1);
空间复杂度 O(N) : 当元素个数为 N 时,最差情况下deque 中保存 N 个元素,使用 O(N) 的额外空间;
作者:jyd
链接:https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/solution/jian-zhi-offer-59-ii-dui-lie-de-zui-da-z-0pap/
内容总结
以上是互联网集市为您收集整理的【java】剑指offer59-II_队列的最大值全部内容,希望文章能够帮你解决【java】剑指offer59-II_队列的最大值所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。