题目链接：https://www.luogu.org/problem/P1886#submit
题意：给定n个数，求大小为k的滑动窗口中最小值和最大值。
思路:单调队列模板题。
AC代码：
#include<cstdio> #include<algorithm> using namespace std; const int maxn=1e6+5; int n,k,head,tail; int a[maxn],q[maxn],p[maxn]; int main(){ scanf("%d%d",&n,&k); for(int i=1;i<=n;++i) scanf("%d",&a[i]); head=1,tail=0; for(int i=1;i<=n;++i){ while(tail>=head&&q[tail]>=a[i]) --tail; q[++tail]=a[i]; p[tail]=i; while(p[head]<=i-k) ++head; if(i>=k) printf("%d ",q[head]); } printf("\n"); head=1,tail=0; for(int i=1;i<=n;++i){ while(tail>=head&&q[tail]<=a[i]) --tail; q[++tail]=a[i]; p[tail]=i; while(p[head]<=i-k) ++head; if(i>=k) printf("%d ",q[head]); } printf("\n"); return 0; }
转载于:https://www.cnblogs.com/FrankChen831X/p/11268652.html
