当前位置:网站首页>[stack and queue topics] - sliding window
[stack and queue topics] - sliding window
2022-04-23 20:22:00 【[email protected]】
deque
1. The concept of double ended queue :
Ordinary queues can delete elements at the head of the queue , Add elements at the end of the team . For double ended queues , At the head of the team 、 The tail of the team can enter and leave the team .
- Out of line and in line at one end , It's kind of like a stack , After the first out
- There are also restricted double ended queues :
You can join the team at one end 、 Out of line operation , The other end can only join the team ;
You can join the team at one end 、 Out of line operation , The other end can only be out of line .
2. Basic operation of double ended queue :
queue.peek() == queue.peekFirst() Check out the team leader element
queue.peekLast() Check out the end of the team elements
queue.add() == queue.addFirst() Add elements from the head of the team
queue.addLast() Add elements from the end of the team
queue.poll() == queue.pollFirst() Delete team leader element
queue.pollLast() Delete end of team element
LeetCode 239: Maximum sliding window
️ Their thinking :
(1) Create a result set array , The size is nums.length - k + 1
(2) Create a double ended queue , Save the index of the elements put in the queue .
If the queue is empty , Then directly put the element index into the queue ; If the queue is not empty , And the new element is larger than the previous element , Then pop up the last element , Then join the current element into the team
because At present The maximum value in the window must not be smaller than the current element to be entered
(3) Determine whether the current maximum value is still in the sliding window , If it's no longer in the window , To pop the index of this element from the head of the queue
(4) Save the maximum value in the window to the result set array
️ Code section :
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
// Special case handling
if(nums == null || nums.length < 2){
return nums;
}
// Result set array
int [] res = new int [nums.length - k + 1];
// Use a double ended queue to save the array index
LinkedList<Integer> queue = new LinkedList();
// Traversal array
for(int i = 0; i < nums.length; i++){
// If the queue is not empty , The current in-line element is smaller than the next queued element , Then pop up the elements in the team
while(!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]){
queue.pollLast();
}
// Queue the index of the current element
queue.addLast(i);
// Determine whether the value in the queue is valid
if(queue.peek() <= i - k){
queue.poll();
}
// Saves the maximum value in the slider to the result set , Mainly control the first input element
if(i + 1 >= k){
res[i - k + 1] = nums[queue.peek()];
}
}
return res;
}
}
版权声明
本文为[[email protected]]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204232021066473.html
边栏推荐
- After route link navigation, the sub page does not display the navigation style problem
- Local call feign interface message 404
- Mathematical modeling column | Part 5: MATLAB optimization model solving method (Part I): Standard Model
- 三十一. `prototype`显示原型属性和`__proto__`隐式原型属性
- Analysis of the relationship between generalized Bim and CAD under the current background
- 堡垒机、跳板机JumpServer的搭建,以及使用,图文详细
- Notes of Tang Shu's grammar class in postgraduate entrance examination English
- 上海回应“面粉官网是非法网站”:疏于运维被“黑”,警方已立案
- Commit and ROLLBACK in DCL of 16mysql
- redis 分布式锁
猜你喜欢
Mysql database backup scheme
Identification of bolt points in aerial photography based on perception
Livego + ffmpeg + RTMP + flvjs to realize live video
堡垒机、跳板机JumpServer的搭建,以及使用,图文详细
AQS learning
SQL Server Connectors By Thread Pool | DTSQLServerTP 插件使用说明
WordPress插件:WP-China-Yes解决国内访问官网慢的方法
A useless confession artifact
PCL点云处理之计算两平面交线(五十一)
Five minutes to show you what JWT is
随机推荐
ArcGIS JS version military landmark drawing (dovetail arrow, pincer arrow, assembly area) fan and other custom graphics
Handwritten Google's first generation distributed computing framework MapReduce
[graph theory brush question-4] force deduction 778 Swimming in a rising pool
The flinkcdc reports an error: but this is no longer available on the server
R语言survival包coxph函数构建cox回归模型、ggrisk包ggrisk函数和two_scatter函数可视化Cox回归的风险评分图、解读风险评分图、基于LIRI数据集(基因数据集)
Five minutes to show you what JWT is
R语言使用timeROC包计算无竞争风险情况下的生存资料多时间AUC值、使用confint函数计算无竞争风险情况下的生存资料多时间AUC指标的置信区间值
WordPress plug-in: WP CHINA Yes solution to slow domestic access to the official website
RT-1052学习笔记 - GPIO架构分析
Local call feign interface message 404
[talkative cloud native] load balancing - the passenger flow of small restaurants has increased
PCL点云处理之计算两平面交线(五十一)
Commit and ROLLBACK in DCL of 16mysql
Click an EL checkbox to select all questions
三十一. `prototype`显示原型属性和`__proto__`隐式原型属性
. Ren -- the intimate artifact in the field of vertical Recruitment!
微信中金财富高端专区安全吗,证券如何开户呢
Modeling based on catiav6
Customize timeline component styles
[problem solving] 'ASCII' codec can't encode characters in position XX XX: ordinal not in range (128)