当前位置:网站首页>【栈和队列专题】—— 滑动窗口
【栈和队列专题】—— 滑动窗口
2022-04-23 20:21:00 【[email protected]】
双端队列
1.双端队列的概念:
普通队列是可以队首删除元素,队尾添加元素。对于双端队列,在队首、队尾都可以进行入队和出队的操作。
- 在一端进行出队和入队的操作,就有点类似栈的意思了,后入先出
- 也存在受限的双端队列:
一端可以入队、出队操作,另一端只能进行入队操作;
一端可以入队、出队操作,另一端只能进行出队操作。
2.双端队列的基本操作:
queue.peek() == queue.peekFirst() 查看队首元素
queue.peekLast() 查看队尾元素
queue.add() == queue.addFirst() 从队首添加元素
queue.addLast() 从队尾添加元素
queue.poll() == queue.pollFirst() 删除队首元素
queue.pollLast() 删除队尾元素
LeetCode 239: 滑动窗口最大值
️ 解题思路:
(1)创建一个结果集数组,大小为nums.length - k + 1
(2)创建一个双端队列,保存放到队列中的元素的索引。
如果队列为空,那么直接将元素索引进入队列;如果队列不为空,而且新进入的元素比上一个元素大,那么弹出上一个元素,再将当前元素入队
因为当前窗口中的最大值肯定不能是比当前待进入元素小的值
(3)判断当前最大值是否还在滑动窗口中,如果已经不再窗口中了,要将这个元素的索引从队首弹出
(4)将窗口中的最大值保存到结果集数组中
️ 代码部分:
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
//特殊情况处理
if(nums == null || nums.length < 2){
return nums;
}
//结果集数组
int [] res = new int [nums.length - k + 1];
//用双端队列来保存数组索引
LinkedList<Integer> queue = new LinkedList();
//遍历数组
for(int i = 0; i < nums.length; i++){
//如果队列不为空,当前对内元素小于下一个入队的元素,那么弹出队内的元素
while(!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]){
queue.pollLast();
}
//将当前元素的索引入队
queue.addLast(i);
//判断队列中的值是否有效
if(queue.peek() <= i - k){
queue.poll();
}
//将滑块中的最大值保存到结果集中,主要控制好第一个录入的元素即可
if(i + 1 >= k){
res[i - k + 1] = nums[queue.peek()];
}
}
return res;
}
}
版权声明
本文为[[email protected]]所创,转载请带上原文链接,感谢
https://blog.csdn.net/qq_61323055/article/details/124359709
边栏推荐
- nc基础用法
- Commit and ROLLBACK in DCL of 16mysql
- 堡垒机、跳板机JumpServer的搭建,以及使用,图文详细
- [graph theory brush question-4] force deduction 778 Swimming in a rising pool
- STM32 Basics
- DTMF双音多频信号仿真演示系统
- Markdown < a > tag new page open link
- SIGIR'22「微软」CTR估计:利用上下文信息促进特征表征学习
- selenium. common. exceptions. WebDriverException: Message: ‘chromedriver‘ executable needs to be in PAT
- Don't bother tensorflow learning notes (10-12) -- Constructing a simple neural network and its visualization
猜你喜欢
CVPR 2022 | QueryDet:使用级联稀疏query加速高分辨率下的小目标检测
Browser - learning notes
【目标跟踪】基于帧差法结合卡尔曼滤波实现行人姿态识别附matlab代码
Operation of numpy array
Zdns was invited to attend the annual conference of Tencent cloud basic resources and share the 2020 domain name industry development report
[graph theory brush question-5] Li Kou 1971 Find out if there is a path in the graph
Openharmony open source developer growth plan, looking for new open source forces that change the world!
aqs的学习
LeetCode动态规划训练营(1~5天)
MySQL advanced lock - overview of MySQL locks and classification of MySQL locks: global lock (data backup), table level lock (table shared read lock, table exclusive write lock, metadata lock and inte
随机推荐
Research on open source OCR engine
Cadence OrCAD capture batch change component packaging function introduction graphic tutorial and video demonstration
What is the difference between a host and a server?
Recommend an open source free drawing software draw IO exportable vector graph
How about CICC fortune? Is it safe to open an account
R语言使用caret包的preProcess函数进行数据预处理:对所有的数据列进行BoxCox变换处理(将非正态分布数据列转换为正态分布数据、不可以处理负数)、设置method参数为BoxCox
Unity 模型整体更改材质
Identification of bolt points in aerial photography based on perception
Don't bother tensorflow learning notes (10-12) -- Constructing a simple neural network and its visualization
ArcGIS js api 4. X submergence analysis and water submergence analysis
Confusion about thread blocking after calling the read () method of wrapper flow
Why does ES6 need to introduce map when JS already has object type
NC basic usage 1
使用 WPAD/PAC 和 JScript在win11中进行远程代码执行1
DNS cloud school | quickly locate DNS resolution exceptions and keep these four DNS status codes in mind
Introduction to link database function of cadence OrCAD capture CIS replacement components, graphic tutorial and video demonstration
R语言ggplot2可视化:ggplot2可视化散点图并使用geom_mark_ellipse函数在数据簇或数据分组的数据点周围添加椭圆进行注释
AQS learning
SQL Server connectors by thread pool 𞓜 instructions for dtsqlservertp plug-in
aqs的学习