有一种题目类型，需要不断查询区间长度为k的子区间内的最小值和最大值，这时候单调队列就出来了，使用单调队列可以很好的解决这一类问题。 什么是单调队列呢？听名字就知道这是一种队列 这种队列支持对头和队尾都能出队，但只能从队尾入队。更为严苛的条件是所有入队的元素必须满足队头到队尾是递减或者递增的，我们可以使用c++自带的stl容器deque来实现这些操作 假设我们现在要创建一个单调递减队列 进来一个数x，我们判断一下队尾元素back是不是大于x的，假如大于，说明back要出队，x要入队，这通过一个while循环就能实现

while(!q.empty()&&q.back()>a[i]) q.pop_back();
q.push_back(a[i]);

然后考虑队头元素，我们知道我们维护的单调递减队列的队头一定是最小的 现在进来一个数字x，我们要维护的是区间长度在x之前的区间长度为k的单调递减队列，因此我们需要判断一下此刻的对头元素和x的距离是不是已经大于窗口的距离了，如果大于，那么我们要将队头元素往后移，以此来维护区间长度。

if(a[i-k]==q.front()) q.pop_front();//如果队尾元素与队首元素的距离大于滑动窗口的距离，说明队首元素不在窗口内，要出队

综上，我们可以写出来一段维护单调递减队列的代码

void get_min()
{
    deque<int >q;
    for(int i=0;i<=n;++i)
    {
        if(i>=k)
        {
            printf("%d ",q.front());
            if(a[i-k]==q.front()) q.pop_front();//如果队尾元素与队首元素的距离大于滑动窗口的距离，说明队首元素不在窗口内，要出队
        }
        while(!q.empty()&&q.back()>a[i]) q.pop_back();
        q.push_back(a[i]);
    }
    puts("");
}

以上是使用deque来进行操作的，但是deque有一个缺点就是deque的常数比手动大，有时候会被卡，这时候就需要我们手动模拟单调队列了 手动模拟单调队列的过程也很简单，还是以创建一个单调递减队列为例 我们开一个minpos数组记录区间长度为k的子区间内，minpos[l]记录子区间的最小值的位置下标，minpos[r]即为队尾的位置下标 其他的操作与deque并无差异 比如要让队尾元素出队，我们只需要让队尾指针r--即可 让x元素入队，即minpos[r++]=x.pos;

while(r>=l&&a[minpos[r]]>=a[i]) r--;
minpos[++r]=i;

然后同理，需要判断一下队头元素和x的距离是否已经大于窗口长度，是的话要将队头指针向后移动

if(r>=l&&i-minpos[l]>=k) l++;//窗口距离大于k的话要出队

综上，我们可以给出例题的全部代码了

#include<iostream>
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<sstream>
#include<stack>
#include<set>
#include<bitset>
#include<vector>
#define ll long long
#define ull unsigned long long
#define up_b upper_bound
#define low_b lower_bound
#define m_p make_pair
#define mem(a) memset(a,0,sizeof(a))
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define INF 0x3f3f3f3f
#define endl '\n'
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const ll mod=1e9+7;
inline int lowbit(int x){return x&(-x);}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){d=a,x=1,y=0;}else{ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}}//x=(x%(b/d)+(b/d))%(b/d);
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0',  ch = getchar();return x*f; }
//inline ll Inverse(ll x) { return qpow(x,mod-2);}
//inline ll C(ll n,ll m) { return fact[n]*inv[m]%mod*inv[n-m]%mod;}
double round(double r){return (r > 0.0) ? floor(r + 0.5) : ceil(r - 0.5);}//四舍五入
const int maxn=1e6+5;
//const int dx[]={-1,0,1,0};
//const int dy[]={0,1,0,-1};
//ll fact[105];
//ll inv[105];
int n,k;
int a[maxn];
int minpos[maxn],maxpos[maxn];
void get_min()
{
	int l=1,r=1;//队头的位置和队尾的位置
	minpos[1]=1;
	if(k==1) printf("%d ",a[1]);
	rep(i,2,n)
	{
		if(r>=l&&i-minpos[l]>=k) l++;//窗口距离大于k的话要出队 
		while(r>=l&&a[minpos[r]]>=a[i]) r--;
		minpos[++r]=i;
		if(i>=k) printf("%d ",a[minpos[l]]);
	}
	puts(""); 
}

void get_max()
{
	int l=1,r=1;
	maxpos[1]=1;
	if(k==1) printf("%d ",a[1]);
	rep(i,2,n)
	{
		if(r>=l&&i-maxpos[l]>=k) l++;
		while(r>=l&&a[maxpos[r]]<=a[i]) r--;
		maxpos[++r]=i;
		if(i>=k) printf("%d ",a[maxpos[l]]);
	}
	puts("");
} 

int main()
{
	n=read(),k=read();
	rep(i,1,n) a[i]=read();
	get_min(),get_max(); 
}
/*
8 3
1 3 -1 -3 5 3 6 7
5 2
 -10 1 2 3 4 5
*/