3.2滑动窗口

滑动窗口***

题目链接
视频讲解
属于单调队列的模板题

如果每次移动窗口，然后在窗口中循环遍历查找最大值，时间复杂度太高
解决思路：
维护一个单调队列，其中head永远指的是当前窗口中最大的值，从head到tail元素递减。
每次移动滑动窗口时，有两种情况：

如果新增加的数大于等于队尾元素，由于新遍历到的数字比队尾元素大，那么在之后的移动中，它一定比队尾元素有用，那么就删除队尾元素，然后暴露出的新的队尾元素再次和新遍历的对比，直到遇到队列中已有的元素比队尾大或者队列中没有元素。（在相等的情况下，因为新遍历到的数字一定更晚被移除去，因此也比队列中已有的数字好）

如果新增加的数小于队尾元素小于队尾元素，因此他就比队列中所有元素都小，不过在以后移动的过程中，可能前面的元素不断出队列，因此他可能会成为大的元素，因此直接进入队列

但是这道题写好之后，犯了一些低级错误：

未注意到数量级是10e6，按照之前做题习惯还是设置了1e5
中间输出换行时，写成了cout<<"\n"<<endl;这玩意是两个换行
未考虑到k=1的特殊情况，其实这样的错误可以通过刚开始直接上k个元素解决，不过我感觉这样不够美观就没有这么写。这说明一件事（在写if条件时候，不仅要注意本身的逻辑判断，还要考虑所用数据结构会不会越界之类的，对于元素的值有着逻辑判断，对元素的下标也应该有一定的约束，如果有确定的条件约束尽量写上）
队列中实际存储的是下标，在部分代码中记得，部分判断代码中却忘记了，直接将a[i]和q[i]进行大小比较了，应该是a[i]和a[q[i]]的比较?

为了容易判断在滑动窗口移动过程中，队列中最大的元素是否已经被移出，队列中实际存储的并不是值，而是下标

在这里插入图片描述文章来源地址https://uudwc.com/A/Ar9r


#include<iostream>

using namespace std;

const int N=1e6+10;
int n,k;
int q[N],a[N];
int head=1; int tail=1;//这里用head指向第一个元素,tail指向队尾元素的下一位 

int main(){
	
	cin>>n>>k;	
	
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	
	//这个是用来求最小的，解析详见后面最大的 
	
	for(int i=1;i<=n;i++){
		//检查当前队头元素是否已经超出窗口范围 
		if(q[head]<=(i-k)&&i>k){
			head++;
		}
		//遍历数组a[]
		if(head==tail||a[i]>q[tail-1]){
			q[tail]=i;			  
			tail++;				 
		}
		else{  
			while(a[i]<=a[q[tail-1]]&&head<tail){
				tail--;
			}
			q[tail]=i; 
			tail++;
		} 
		//前几个不打印 
		if(i>=k){
			cout<<a[q[head]]<<" ";
		}
	}
	
	cout<<"\n";
	
	head=tail=1;//初始化 
	
	for(int i=1;i<=n;i++){
		//检查当前队头元素是否已经超出窗口范围 
		if(q[head]<=(i-k)){
			head++;
		}
		//遍历数组a[]
		if(head==tail||a[i]<q[tail-1]){//如果当前队列为空，或者遍历的元素小于队尾元素，
			q[tail]=i;			  //注意队尾是tail-1，那么直接把元素(下标)放进去 
			tail++;				 
		}
		else{ //如果当前遍历元素更大或等于，那就在队列中删除直到找到一个比当前元素更大的 
			while(a[i]>=a[q[tail-1]]&&head<tail){
				tail--;
			}
			q[tail]=i;//这里为何是tail自己画个图看下 
			tail++;//因为tail始终指向的是队列中最后一个元素的下一位 
		} 
		//前几个不打印 
		if(i>=k){
			cout<<a[q[head]]<<" ";
		}
	}
	
	
	return 0;
}