洛谷 - P1886 滑动窗口(单调队列/线段树)_洛谷1886

题目链接：点击查看

题目大意：给出一个由n个数构成的序列，再给出一个长度为k的窗口，这个窗口从第一个下标开始一直向后移动，每次移动一个单位，每次移动询问一次该窗口中的最大值和最小值，最后输出答案

题目分析：看似是一个模拟，其实暴力模拟肯定会爆，因为涉及到区间最值问题，而且还是静态的询问，所以这个题目有三种方法可以解决，分别是st表，线段树和单调队列，因为st表我不会优化，所以有五个测试点MLE了，这里就不用那个方法了，线段树的话空间复杂度比起st表一般是能小上5倍左右，但时间复杂度每一次查询时要多logn的常数，所以酌情考虑吧，用线段树的话就不会MLE了，擦边把这个题目给A了，一会也放一下代码，没什么好说的，主要是来说一下单调队列来做这个题目，之前只是学过单调栈，今天接触了一下单调队列，发现还是挺简单的，主要原理就是用双端队列维护一个严格递增或严格递减的序列，每次增加一个新值的时候，将其与尾部比较，最终插入尾部，当使用的时候，是使用头部的数值，大概就是这样了，一会看代码理解一下吧

然后这个题目还需要维护一下每个数值所代表的id，用来判断该数值在当前区间中是否过期，若过期的话直接舍弃掉即可

当然三种方法的复杂度来比较一下吧：

st表：空间复杂度nlogn，时间复杂度：打表nlogn，查询O(1)

线段树：空间复杂度n*4，时间复杂度：建树nlogn，查询nlogn

单调队列：空间复杂度n，时间复杂度：n

吐槽一句：这个题目本来是poj上的题目，为什么跑来洛谷做呢，三种方法，st表MLE，线段树TLE，单调队列还不支持C++11，我：？？？？

代码：

单调队列（deque）：

#include<iostream>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<cmath>
#include<cctype>
#include<stack>
#include<queue>
#include<list>
#include<vector>
#include<set>
#include<map>
#include<sstream>
#include<deque>
using namespace std;
 
typedef long long LL;
 
const int inf=0x3f3f3f3f;
 
const int N=1e6+100;
 
struct Node
{
	int val,id;
}a[N];
 
int ans_max[N],ans_min[N];
 
int main()
{
//	freopen("input.txt","r",stdin);
//	ios::sync_with_stdio(false);
	int n,k;
	while(scanf("%d%d",&n,&k)!=EOF)
	{
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i].val);
			a[i].id=i;
		}
		deque<Node>mmax;//维护最大值的单调队列
		deque<Node>mmin;//维护最小值的单调队列
		for(int i=1;i<=k-1;i++)//预处理1~k-1的值
		{
			while(mmax.size()&&mmax.back().val<=a[i].val)//将比当前值小的数全删掉（尾部）
				mmax.pop_back();
			mmax.push_back(a[i]);
			while(mmin.size()&&mmin.back().val>=a[i].val)//将比当前值大的数全删掉（尾部）
				mmin.pop_back();
			mmin.push_back(a[i]);
		}
		for(int i=k;i<=n;i++)//枚举滑动窗口的末尾位置
		{
			int left=i-k+1;//记录滑动窗口的首位置
			while(mmax.size()&&mmax.back().val<=a[i].val)//将比当前值小的数全删掉（尾部）
				mmax.pop_back();
			mmax.push_back(a[i]);
			while(mmin.size()&&mmin.back().val>=a[i].val)//将比当前值大的数全删掉（尾部）
				mmin.pop_back();
			mmin.push_back(a[i]);
			while(mmax.size()&&mmax.front().id<left)//将过期的值删掉（头部）
				mmax.pop_front();
			while(mmin.size()&&mmin.front().id<left)//将过期的值删掉（头部）
				mmin.pop_front();
			ans_max[left]=mmax.front().val;//更新答案
			ans_min[left]=mmin.front().val;
		}
		printf("%d",ans_min[1]);
		for(int i=2;i+k-1<=n;i++)
			printf(" %d",ans_min[i]);
		printf("\n%d",ans_max[1]);
		for(int i=2;i+k-1<=n;i++)
			printf(" %d",ans_max[i]);
		printf("\n");
	}
	
	
	
	
	
	
	
     
     
     
     
      
     
    return 0;
}

单调队列（模拟）：专门给poj2823改的代码

#include<iostream>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<cmath>
#include<cctype>
#include<stack>
#include<list>
#include<vector>
#include<set>
#include<map>
#include<sstream>
using namespace std;
 
typedef long long LL;
 
const int inf=0x3f3f3f3f;
 
const int N=1e6+100;
 
struct Node
{
	int val,id;
}t[N];
 
int a[N];
 
int main()
{
//	freopen("input.txt","r",stdin);
//	ios::sync_with_stdio(false);
	int n,k;
	while(scanf("%d%d",&n,&k)!=EOF)
	{
		for(int i=1;i<=n;i++)
			scanf("%d",a+i);
		int l=1,r=0;
		for(int i=1;i<=n;i++)
		{
			int left=i-k+1;
			while(l<=r&&t[l].id<left)
				l++;
			while(l<=r&&t[r].val>=a[i])
				r--;
			t[++r].val=a[i];
			t[r].id=i;
			if(i>=k)
				printf("%d ",t[l].val);
		}
		printf("\n");
		l=1,r=0;
		for(int i=1;i<=n;i++)
		{
			int left=i-k+1;
			while(l<=r&&t[l].id<left)
				l++;
			while(l<=r&&t[r].val<=a[i])
				r--;
			t[++r].val=a[i];
			t[r].id=i;
			if(i>=k)
				printf("%d ",t[l].val);
		}
		printf("\n");
	}
	
	
	
	
	
	
	
     
     
     
     
      
     
    return 0;
}

线段树：

#include<iostream>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<cmath>
#include<cctype>
#include<stack>
#include<queue>
#include<list>
#include<vector>
#include<set>
#include<map>
#include<sstream>
using namespace std;
 
typedef long long LL;
 
const int inf=0x3f3f3f3f;
 
const int N=1e6+100;
 
int ans1[N],ans2[N];
 
struct Node
{
	int l,r,mmax,mmin;
}tree[N<<2];
 
void build(int k,int l,int r)
{
	tree[k].l=l;
	tree[k].r=r;
	if(l==r)
	{
		scanf("%d",&tree[k].mmin);
		tree[k].mmax=tree[k].mmin;
		return;
	}
	int mid=l+r>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	tree[k].mmax=max(tree[k<<1].mmax,tree[k<<1|1].mmax);
	tree[k].mmin=min(tree[k<<1].mmin,tree[k<<1|1].mmin);
}
 
int query_max(int k,int l,int r)
{
	if(tree[k].r<l||tree[k].l>r)
		return -inf;
	if(tree[k].r<=r&&tree[k].l>=l)
		return tree[k].mmax;
	return max(query_max(k<<1,l,r),query_max(k<<1|1,l,r));
}
 
int query_min(int k,int l,int r)
{
	if(tree[k].r<l||tree[k].l>r)
		return inf;
	if(tree[k].r<=r&&tree[k].l>=l)
		return tree[k].mmin;
	return min(query_min(k<<1,l,r),query_min(k<<1|1,l,r));
}
 
int main()
{
//	freopen("input.txt","r",stdin);
//	ios::sync_with_stdio(false);
	int n,k;
	while(scanf("%d%d",&n,&k)!=EOF)
	{
		build(1,1,n);
		for(int i=1;i+k-1<=n;i++)
		{
			ans1[i]=query_min(1,i,i+k-1);
			ans2[i]=query_max(1,i,i+k-1);
		}
		printf("%d",ans1[1]);
		for(int i=2;i+k-1<=n;i++)
			printf(" %d",ans1[i]);
		printf("\n%d",ans2[1]);
		for(int i=2;i+k-1<=n;i++)
			printf(" %d",ans2[i]);
		printf("\n");
	}
	
	
	
	
	
	
	
     
     
     
     
      
     
    return 0;
}