当前位置:网站首页>Leetcode sword finger offer 59 - ii Maximum value of queue
Leetcode sword finger offer 59 - ii Maximum value of queue
2022-07-06 01:11:00 【May Hacker】
subject
Please define a queue and implement the function max_value Get the maximum in the queue , Function required max_value、push_back and pop_front The average time complexity of is O(1).
If the queue is empty ,pop_front and max_value Need to return -1
Example 1:
Input :
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
Output : [null,null,null,2,1,2]
Example 2:
Input :
["MaxQueue","pop_front","max_value"]
[[],[],[]]
Output : [null,-1,-1]
Limit :
1 <= push_back,pop_front,max_value Total number of operations for <= 10000
1 <= value <= 10^5
source : Power button (LeetCode)
link :https://leetcode.cn/problems/dui-lie-de-zui-da-zhi-lcof
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Ideas
- Pay special attention if Java Be familiar with this topic Deque and Queue Of API, about Deque Come on , It can be a queue or a stack , This topic will be used as a queue , So to view the tail element, you should use PeekLast(), instead of Peek(), because Peek() amount to PeekFirst()
- Maintain an additional two-way queue that holds the maximum value , From head to tail , It should be in reverse order , That is, when the element at the end of the team is smaller than the element currently entering the team , want while Pop up these small elements , So as to ensure that it is in reverse order
- When you push the stack , Just judge whether the heads of the two queues are equal , If it is equal, the reverse two-way queue will also pop up .
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(); */
边栏推荐
- Unity | 实现面部驱动的两种方式
- CTF daily question day44 rot
- Cglib dynamic agent -- example / principle
- IP storage and query in MySQL
- A preliminary study of geojson
- Illustrated network: the principle behind TCP three-time handshake, why can't two-time handshake?
- Recursive method converts ordered array into binary search tree
- Starting from 1.5, build a micro Service Framework - call chain tracking traceid
- MYSQL---查询成绩为前5名的学生
- Lone brave man
猜你喜欢
激动人心,2022开放原子全球开源峰会报名火热开启
Introduction to robotics I. spatial transformation (1) posture, transformation
Daily practice - February 13, 2022
Four dimensional matrix, flip (including mirror image), rotation, world coordinates and local coordinates
Recommended areas - ways to explore users' future interests
After 95, the CV engineer posted the payroll and made up this. It's really fragrant
Blue Bridge Cup embedded stm32g431 - the real topic and code of the eighth provincial competition
SAP Spartacus home 页面读取 product 数据的请求的 population 逻辑
Cf:h. maximum and [bit operation practice + K operations + maximum and]
Vulhub vulnerability recurrence 74_ Wordpress
随机推荐
Opinions on softmax function
毕设-基于SSM高校学生社团管理系统
[groovy] compile time metaprogramming (compile time method injection | method injection using buildfromspec, buildfromstring, buildfromcode)
The value of applet containers
Cf:d. insert a progression [about the insert in the array + the nature of absolute value + greedy top-down]
Installation and use of esxi
curlpost-php
面试必刷算法TOP101之回溯篇 TOP34
在产业互联网时代,将会凭借大的产业范畴,实现足够多的发展
WGet: command line download tool
详细页返回列表保留原来滚动条所在位置
关于#数据库#的问题:(5)查询库存表中每本书的条码、位置和借阅的读者编号
Hcip---ipv6 experiment
ubantu 查看cudnn和cuda的版本
[groovy] JSON string deserialization (use jsonslurper to deserialize JSON strings | construct related classes according to the map set)
MCU通过UART实现OTA在线升级流程
基於DVWA的文件上傳漏洞測試
Construction plan of Zhuhai food physical and chemical testing laboratory
Leetcode daily question solution: 1189 Maximum number of "balloons"
golang mqtt/stomp/nats/amqp