当前位置:网站首页>Leetcode 剑指 Offer 59 - II. 队列的最大值
Leetcode 剑指 Offer 59 - II. 队列的最大值
2022-07-06 01:10:00 【May Hacker】
题目
请定义一个队列并实现函数 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
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/dui-lie-de-zui-da-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
- 特别注意如果用Java做本题要熟悉Deque和Queue的API,对于Deque来说,能当队列也能当栈,本题会当队列来用,所以查看尾部元素应该用PeekLast(),而不是Peek(),因为Peek()相当于PeekFirst()
- 额外维护一个保存最大值的双向队列,从队头到队尾,应该是逆序的,即当队尾元素小于当前要进队的元素时,要while弹出去这些小元素,从而保证是逆序的
- 出栈的时候,只需要判断一下两个队列的队头是否相等,相等则把这个逆序双向队列也弹出。
Java AC
class MaxQueue {
private Queue<Integer> q = new LinkedList<>();
private Deque<Integer> dq = new LinkedList<>();
public MaxQueue() {
}
public int max_value() {
if(q.isEmpty()){
return -1;
}
return dq.peekFirst();
}
public void push_back(int value) {
q.add(value);
while(!dq.isEmpty()&& dq.peekLast()<value){
dq.removeLast();
}
dq.add(value);
}
public int pop_front() {
if(q.isEmpty()){
return -1;
}
int res = q.poll();
if(dq.peekFirst()==res){
dq.removeFirst();
}
return res;
}
}
/** * 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(); */
边栏推荐
- File upload vulnerability test based on DVWA
- KDD 2022 | EEG AI helps diagnose epilepsy
- RAID disk redundancy queue
- 直播系统代码,自定义软键盘样式:字母、数字、标点三种切换
- Unity | 实现面部驱动的两种方式
- 现货白银的一般操作方法
- 95后CV工程师晒出工资单,狠补了这个,真香...
- Recommended areas - ways to explore users' future interests
- IP storage and query in MySQL
- Programmer growth Chapter 9: precautions in real projects
猜你喜欢
Ubantu check cudnn and CUDA versions
File upload vulnerability test based on DVWA
Keepalive component cache does not take effect
After Luke zettlemoyer, head of meta AI Seattle research | trillion parameters, will the large model continue to grow?
SSH login is stuck and disconnected
[pat (basic level) practice] - [simple mathematics] 1062 simplest fraction
Test de vulnérabilité de téléchargement de fichiers basé sur dvwa
Four commonly used techniques for anti aliasing
WordPress collection plug-in automatically collects fake original free plug-ins
Fibonacci number
随机推荐
vSphere实现虚拟机迁移
synchronized 和 ReentrantLock
Finding the nearest common ancestor of binary tree by recursion
关于softmax函数的见解
几百行代码实现一个 JSON 解析器
The inconsistency between the versions of dynamic library and static library will lead to bugs
Live broadcast system code, custom soft keyboard style: three kinds of switching: letters, numbers and punctuation
视频直播源码,实现本地存储搜索历史记录
Test de vulnérabilité de téléchargement de fichiers basé sur dvwa
Building core knowledge points
激动人心,2022开放原子全球开源峰会报名火热开启
devkit入门
[groovy] JSON string deserialization (use jsonslurper to deserialize JSON strings | construct related classes according to the map set)
Why can't mathematics give machine consciousness
Four commonly used techniques for anti aliasing
现货白银的一般操作方法
Zhuhai's waste gas treatment scheme was exposed
The value of applet containers
Gartner released the prediction of eight major network security trends from 2022 to 2023. Zero trust is the starting point and regulations cover a wider range
Zhuhai laboratory ventilation system construction and installation instructions