题解：P1886 滑动窗口 /【模板】单调队列

关于单调队列，有一句名言。

如果一个人比你小，还比你强，那你就没救了。

事实上，单调队列确实是这个样子的。

因为当出现一个数比

x

大，还比你晚出现，那代表在包含

x

的区间内，这个数一直比

x

大，而且

x

肯定比这个数先离开区间，那你接下来就不会被输出，不必存储。

单调队列，正是那样，队列里的元素是单调的。

根据上面的说法，容易给出单调队列的写法，我们以维护窗口最大值为例：

弹出过时的元素；
当队尾元素 $<$ 新加入的元素时，弹出队尾元素；
重复操作 $2$ ，直到队列为空或队尾元素 $>$ 新加入的元素；
队首元素就是当前答案；
移动窗口。

这里根据我们开头的性质，容易得出答案一定正确。

求最小值同理。

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,l=1,r=0;
int a[1000005],q[1000005];
signed main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}for(int i=1;i<=n;i++){
		while(l<=r&&a[q[r]]>=a[i]){
			r--;
		}q[++r]=i;
		while(l<=r&&q[l]+k<=i){
			l++;
		}if(i>=k){
			cout<<a[q[l]]<<" ";
		}
	}cout<<"\n";
	l=1,r=0;
	for(int i=1;i<=n;i++){
		while(l<=r&&a[q[r]]<=a[i]){
			r--;
		}q[++r]=i;
		while(l<=r&&q[l]+k<=i){
			l++;
		}if(i>=k){
			cout<<a[q[l]]<<" ";
		}
	}
	return 0;
}

这里不推荐使用双端队列，建议使用手写队列。

注意代码里往队列里插入的是下标而不是元素本身的值。

题解：P1886 滑动窗口 /【模板】单调队列

文章操作

相关推荐

评论

题解：P1886 滑动窗口 /【模板】单调队列