首先推荐一篇对我非常有益的BOLG。
这一题分两个部分最小值和最大值，做法本质相同。结构体node中的v记录的是价值，pos记录的是位置，h代表队头指针，t代表队尾指针，h和t在两个部分是分别独立的，所以要分别赋初值，这是实现单调队列的第一题，不怎么会口糊。
#include<bits/stdc++.h> using namespace std; const int N=1e6+5; int n,k,h,t,a[N]; struct node { int v,pos; }Q[N]; int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d",&a[i]); h=1;t=0; for(int i=1;i<=n;i++) { while(h<=t&&Q[h].pos+k<=i) h++; while(h<=t&&Q[t].v>=a[i]) t--; Q[++t].v=a[i]; Q[t].pos=i; if(i>=k) printf("%d ",Q[h].v); } h=1;t=0; puts(""); for(int i=1;i<=n;i++) { while(h<=t&&Q[h].pos+k<=i) h++; while(h<=t&&Q[t].v<=a[i]) t--; Q[++t].v=a[i]; Q[t].pos=i; if(i>=k) printf("%d ",Q[h].v); } puts(""); return 0; }
原文：https://www.cnblogs.com/Siv0106/p/11741927.html