先放上luogu的题目链接——
然后我们再来讲单调队列
单调队列是指这样一种队列：在队列中的元素为单调递增状态或单调递减状态。
例如1 2 3 4 5和9 2 1都是单调队列，但1 2 2 3 4和4 3 4 5就不是单调队列。
但普通队列明显是维持不了单调队列的性质的。
为了维持单调队列的单调性质，我们只好想一些方法。方法就是修改队列的性质。单调队列不仅队头可以出队，队尾也可以出队。
比如说有一个单调队列是 1 3 7 8
现在突然要从队尾进来一个6
如果单纯的把6插进队尾的话，那这个队列就变成1 3 7 8 6 就不是单调队列了对不对所以这时候我们要让队尾出队，把8退出去。让这个队列变成1 3 7
但是发现这时候队尾7还是大于6，如果要把6入队的话还是满足不了单调队列的性质。
所以再让队尾出队，这时候队列变成1 3，6可以入队了
于是入队操作进行完之后单调队列就变成了1 3 6
所以单调队列的入队操作算法呼之欲出对不对
while(t>=h&&queue[t]>input) t--;
按这个算法我们就得到一个单调队列
单调队列做滑稽窗口的做法是这样的(只讲MAX了，MIN同理)
假设我们的滑稽窗口划着划着，突然划进来一个很大的数，比前面所有的数都要大
这时候我们发现，如果滑稽窗口不接受一个更大的数的话，不管进来什么数，只要这个MAX仍然在滑稽窗口里 ，它就是最大值
于是我们就把滑稽窗口划分成两个部分：max左面的数和max右面的数。
max左面的数，随着滑稽窗口自然滑动。等什么时候划出去了就出队。这个不用管它。
max右面的数，只有在max出去之后才有价值。
所以输入一个数，先比较它跟单调队列队尾，如果不符合单调队列的性质就让队尾出队。
再讲一下pos是干嘛的
pos[]用来记录单调队列中的元素原来在序列的哪个位置，即元素在原序列中的下标
这个数组主要是用来判断单调队列的元素什么时候该出队的。因为单调队列不光队头可以出队，队尾同样也可以出队，所以单调队列的元素在原序列中不是按下标排好队的因此我们单独设一个pos好知道到底什么时候应该出队最后，设h是队头，当发现pos[h]==i-m+1的时候，说明队列里f[h]这个元素快滑出窗口出去了，因此h++让队头出队放一下滑稽窗口的代码
#include#include #include inline long long read(){ long long num=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)){ num=num*10+ch-'0'; ch=getchar(); } return num*f;}struct file{ int f[2000000]; int pos[2000000]; int ans[2000000]; int h,t; file(){h=1;}}maxx,minn;int main(){ int n=read(),k=read(); int a; for(int i=1;i<=n;++i){ a=read(); while(maxx.f[maxx.t]<=a&&maxx.t>=maxx.h) maxx.t--; maxx.f[++maxx.t]=a; maxx.pos[maxx.t]=i; while(minn.f[minn.t]>=a&&minn.t>=minn.h) minn.t--; minn.f[++minn.t]=a; minn.pos[minn.t]=i; if(i>=k){ maxx.ans[i]=maxx.f[maxx.h]; minn.ans[i]=minn.f[minn.h]; if(maxx.pos[maxx.h]==i-k+1) maxx.h++; if(minn.pos[minn.h]==i-k+1) minn.h++; } } for(int i=k;i<=n;++i) printf("%d ",minn.ans[i]); printf("\n"); for(int i=k;i<=n;++i) printf("%d ",maxx.ans[i]); return 0;}
就这么多