不清楚蓝桥杯考什么的点点下方👇
考点秘籍
想背纯享模版的伙伴们点点下方👇
蓝桥杯省一你一定不能错过的模板大全(第一期)
蓝桥杯省一你一定不能错过的模板大全（第二期）
蓝桥杯省一你一定不能错过的模板大全（第三期）
蓝桥杯省一你一定不能错过的模板大全（第四期）！！！
想背注释模版的伙伴们点点下方👇
蓝桥杯必背第一期
蓝桥杯必背第二期
往期精彩回顾
蓝桥杯上岸每日N题 第一期(一)！！！
蓝桥杯上岸每日N题第一期(二)！！！
蓝桥杯上岸每日N题第一期(三)！！！
蓝桥杯上岸每日N题第二期(一)！！！
蓝桥杯上岸每日N题第三期(一)！！！
蓝桥杯上岸每日N题 第四期(最少刷题数)！！！
蓝桥杯上岸每日N题 第五期(山)！！！
蓝桥杯上岸每日N题 第六期(求阶乘)！！！
蓝桥杯上岸每日N题 第七期(小猫爬山)！！！
蓝桥杯上岸每日N题 第八期 (全球变暖)！！！
操作系统期末题库 第九期(完结)
LeetCode Hot100 刷题(第三期)
idea创建SpringBoot项目报错解决方案
数据库SQL语句（期末冲刺）
想看JavaB组填空题的伙伴们点点下方 👇
填空题
竞赛干货
算法竞赛字符串常用操作大全
蓝桥杯上岸必刷！！！(模拟/枚举专题)
蓝桥杯上岸必背！！！ (第三期 DP)
蓝桥杯上岸必背！！！(第四期DFS)
蓝桥杯上岸必背！！！(第五期BFS)
蓝桥杯上岸必背！！！(第六期树与图的遍历)
蓝桥杯上岸必背！！！(第七期 最短路算法)
蓝桥杯上岸必背！！！(第八期 简单数论)
蓝桥杯上岸必刷！！！(进制、数位专题)
蓝桥杯上岸考点清单 (冲刺版）！！！
数组模拟单调队列
分析
以k=3举例：
(1)利用单调队列的性质：
<1>最小值：确保队列单调递增，处理后，队头即是最小值。
<2>最大值：确保队列单调递减，处理后，队头即是最大值。
那么怎么确保单调性？
关键代码：
以最小值为例：while(hh<=tt&&a[q[tt]]>=a[i])tt--;
(2)这里的a[q[tt]]>=a[i]即是确保单调性的关键！
（求最大值这里修改成a[q[tt]]<=a[i]，确保单调递减即可，其余均一致。)
解读：每次添加元素到队尾后，将该队尾元素和队头元素进行比较，如果这个元素大于(等于)队头元素，就说明队尾元素并不是需要的最小值，队头元素比它更适合，更有潜力成为最小值，所以将该队尾元素抹掉，则t- -。再继续添加，继续判断。
换句话来说，不满足单调递增的性质，需要将不满足的元素给剔掉，确保单调性。
确保单调性后，为什么输出队头即可?
确保单调性后，我们得到的队尾元素即是最小/大值，此时，如果只有一个元素，即队头，输出队头即可。
如果还有剩余元素，需要将队列中剩余的其他元素剔掉，让队列中只有一个元素，此时，队头指向队尾，输出队头即可。
综上，输出队头即可。
那又怎么剔掉单调处理后，队列中还有多余的元素(出队多余元素）？
关键代码：
以最小值为例：if(hh<=tt&&i-k+1>q[hh])hh++;
(3)这里的i-k+1即是确保出队的关键！
推断如下：
这里的出队有两层意义：
<1>用于更新原队列的hh，一个个出掉，范围更新下去。
<2>用于队头元素的出队，如果tt- -后,队列中只有1个元素，即队头，输出即可。
如果队列中还剩1、2个元素,则需要出队，不断出掉队尾元素前的元素，即hh++；
(4)最后，由单调性的确保和队头元素的确保，只需要输出队头元素即可。
队列过程变化图
图1
文章来源：https://www.toymoban.com/news/detail-634914.html
图2
文章来源地址https://www.toymoban.com/news/detail-634914.html
代码
import java.util.*;
import java.io.*;
public class Main{
static int N=100010;
static int n,k;
static int hh,tt;
static int q[]=new int [N];
static int a[]=new int [N];
public static void main(String []args) throws IOException{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
String []st = in.readLine().split(" ");
n=Integer.parseInt(st[0]);
k=Integer.parseInt(st[1]);
String []str = in.readLine().split(" ");
for(int i=0;i<n;i++){
a[i]=Integer.parseInt(str[i]);
}
hh = 0;
tt=-1;
//求最小值
for(int i=0;i<n;i++){
//出队
if(hh<=tt&&i-k+1>q[hh])hh++;//出队
//t--更新到最后，如果还剩1-2个元素，则把他们都剔掉。
//此时，队头指向队尾，再输出队头即可。
while(hh<=tt&&a[q[tt]]>=a[i])tt--;//保证队列单调递增，那么队尾即是最小值。
//具体为添加进队尾的元素如果比队头的元素要大，就tt--，即把该元素给剔掉。
q[++tt]=i;//添加元素下标到队列尾
if(i>=k-1)//在k的范围队列中，输出元素
out.print(a[q[hh]]+" ");
}
out.println();
//求最大值
hh=0;
tt=-1;
for(int i=0;i<n;i++){
//出队
if(hh<=tt&&i-k+1>q[hh])hh++;
//t--更新到最后，如果还剩1-2个元素，则把他们都剔掉。
//此时，队头指向队尾，再输出队头即可。
while(hh<=tt&&a[q[tt]]<=a[i])tt--;//保证队列单调递减，那么队尾即是最大值。
//具体为添加进队尾的元素如果比队头的元素要小，就tt--，即把该元素给剔掉。
q[++tt]=i;//添加元素下标到队列尾
if(i>=k-1)//在k的范围队列中，输出元素
out.print(a[q[hh]]+" ");
}
out.flush();
}
}
到了这里，关于滑动窗口（全面清晰/Java）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
