首页 > 代码库 > WINDOW（单调队列的应用）
WINDOW（单调队列的应用）
给你一个长度为 N 的数组，一个长为 K 的滑动的窗体从最左移至最右端，
你只能见到窗口的K个数，每次窗体向右移动一位，如下表：
你的任务是找出窗口在各位置时的 max value,min value.
INPUT：
第 1 行 n,k,
20%：n<=500;
50%: n<=100000;
100%: n<=1000000;
第 2 行为长度为 n 的数组
8 3
1 3 -1 -3 5 3 6 7
OUTPUT：
2 行，
第 1 行每个位置的 min value,
第 2 行每个位置的 max value
-1 -3 -3 -3 3 3
3 3 5 5 6 7
题解：
如果每次都要sort的话，小数据可以O（n*k），但是数据大的话一定会超时。
那么该如何搞呢？ 单调队列。O（n）效率很高！！
单调队列，一个元素单调的队列，可以保证队头是最小（最大）的；
可以通过队首删除，队尾插入来维护最优值。
这道题，就是通过单调队列来维护一个最大值和最小值。
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<string> 6 #include<algorithm> 7 #include<queue> 8 #include<cstdlib> 9 #include<iomanip>10 #include<ctime>11 using namespace std;12 const int maxn=5000001;13 int n,k;14 int a[maxn],q[maxn];15 int tail=0,head=0;16 17 int main()18 {19 cin>>n>>k;20 for(int i=1;i<=n;i++)21 cin>>a[i];22 q[tail]=1;23 for(int i=2;i<k;i++)24 {25 while(a[i]<a[q[tail]]&&tail>=head)26 {27 tail--;28 }29 q[++tail]=i;30 }31 for(int i=k;i<=n;i++)32 {33 if(i-q[head]==k) head++;34 while(a[i]<a[q[tail]]&&tail>=head)35 {36 tail--;37 }38 q[++tail]=i;39 cout<<a[q[head]]<<" ";40 }41 cout<<endl;42 memset(q,0,sizeof(q));43 head=0,tail=0;44 q[tail]=1;45 for(int i=2;i<k;i++)46 {47 while(a[i]>a[q[tail]]&&tail>=head)48 {49 tail--;50 }51 q[++tail]=i;52 }53 for(int i=k;i<=n;i++)54 {55 if(i-q[head]==k) head++;56 while(a[i]>a[q[tail]]&&tail>=head)57 {58 tail--;59 }60 q[++tail]=i;61 cout<<a[q[head]]<<" ";62 }63 cout<<endl;64 return 0;65 }
WINDOW（单调队列的应用）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。