题意

求滑动窗口内的最小值和最大值

思路

首先，暴力肯定会 TLE（范围 $n^2$，时间 $O(n^2)$）。有没有什么方法让每次滑动窗口后保留之前的最小和最大值呢？

这时我们发现单调队列很符合我们的需求，新的数和队列里的“前辈”比较就可以了

但是，窗口滑动后怎么踢掉不合法的数呢？

我们可以新开一个数组，与队列数组用同一个头尾指针。这个数组存队列里元素在原数组的下标，当它们不合法时就踢掉

最后就是输出 + AC 啦

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
int a[N];
int q1[N],q2[N];	// 单调队列
int q1f,q1b;	// front 和 back
int q2f,q2b;
int mx[N],mn[N];	// 答案
int h1[N],h2[N];	// 标记窗口位置
int main(int argc, char **argv){
	int n,k;
	cin >> n >> k;
	for (int i = 1;i <= n;i++){
		cin >> a[i];

		// 最大值
		// 以大到小为规则排序
		while (q1f <= q1b && a[i] >= q1[q1b])	q1b--;
		q1[++q1b] = a[i];
		h1[q1b] = i;
		// 踢掉不合法的数
		while (h1[q1f] <= i - k)	q1f++;
		// 窗口位置合法时开始记录
		if (i >= k)	mx[i] = q1[q1f];

		// 最小值
		// 以小到大为规则排序，其余同上
		while (q2f <= q2b && a[i] <= q2[q2b])	q2b--;
		q2[++q2b] = a[i];
		h2[q2b] = i;
		while (h2[q2f] <= i - k)	q2f++;
		if (i >= k)	mn[i] = q2[q2f];
	}
	for (int i = k;i <= n;i++){
		printf("%d ",mn[i]);
	}
	cout << '\n';
	for (int i = k;i <= n;i++){
		printf("%d ",mx[i]);
	}
	return 0;
}

我的题解

思路

很简单先求区间最大再求区间最小 两个代码之间只有一个符号差别大家可以看看 只用维护单调递增和递减就可以啦

#include<bits/stdc++.h>
using namespace std;
int q[1000005],a[20000000],front,rr,n,k;
void zry(){//这个是求区间最大值
front=1; //先赋值队头
rr=0;
for(int i=1;i<=n;i++) {
	while(q[front]<=i-k&&front<=rr){
	//这个是为了保证队头在窗口内
	front++;//不断移动窗口 
}
while(front<=rr&&a[q[rr]]>=a[i])//维护单调递减
rr--;
q[++rr] =i;//入队
if(i>=k)
cout<<a[q[front]] <<" ";
}
cout<<endl;
}
void min(){
	front =1;
	rr=0;
for(int i=1;i<=n;i++) {
	while(q[front]<=i-k&&front<=rr){
	//这个是为了保证队头在窗口内
	front++;//不断移动窗口 
}
while(front<=rr&&a[q[rr]]<=a[i])//维护单调递增 
rr--;
q[++rr] =i;//入队
if(i>=k)
cout<<a[q[front]] <<" ";
}
cout<<endl;
}

int main(){
cin>>n>>k;
for(int i=1;i<=n;i++) {
	cin>>a[i];
}
zry() ;
min();
return 0;

}

搞两个单调队列，一个max，一个min

#include<iostream>
#include<queue>
using namespace std;
int n,k;
int mi[1145141],mif=0,mib=0;
int ma[1145141],maf=0,mab=0;
int mis[1145141];
int mas[1145141];
int mip[1145141];
int map[1145141];
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		
		while(mif<=mib && mi[mib]>=x)
		{
			mib--;
		}
		mi[++mib]=x;
		mip[mib]=i;
		while(mip[mif]<=i-k)mif++;
		if(i>=k)mis[i]=mi[mif];
		
		while(maf<=mab && ma[mab]<=x)
		{
			mab--;
		}
		ma[++mab]=x;
		map[mab]=i;
		while(map[maf]<=i-k)maf++;
		if(i>=k)mas[i]=ma[maf];
	}
	for(int i=k;i<=n;i++)
	{
		cout<<mis[i]<<" ";
	}
	cout<<"\n";
	for(int i=k;i<=n;i++)
	{
		cout<<mas[i]<<" ";
	}
	return 0;
}