假设当前我们要找的是区间最大值，我们可以看到：当新进入的元素大于当前区间最大值，那么它就有可能成为这段区间的最大值也就是要把当前最大值杀死。如果后续进入的是小于当前最大值的那么在最大值出去之后，它就可能成为最大值.也就是说我们发现这个东西具有单调性,所以我们就可以运用单调队列的思维来思考,我们需要使用优先队列,原因是我们需要去除队首和队尾 这个道理同样适用于找区间最小值. 然后是关于存储内容的问题.如果直接存储数值,我们不会知道当前存到第几个元素了,也就是不知道什么时候队首出队.因此我们存储的是下标.当然也可以使用pair类型来存储数据

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e6+10;
deque<int>q1,q2;
int n,k;
int a[N];
int main()
{
	cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)
    {
    	if(!q1.empty()&&i-q1.front()>=k)q1.pop_front();//当前队列不够大了,超出了长度,所以需要队首出队
        while(!q1.empty()&&a[q1.back()]>=a[i])q1.pop_back();
        q1.push_back(i);
        if(i>=k)cout<<a[q1.front()];
    }
    cout<<endl;
     for(int i=1;i<=n;i++)
    {
    	if(!q2.empty()&&i-q2.front()>=k)q2.pop_front();//当前队列不够大了,超出了长度,所以需要队首出队
        while(!q2.empty()&&a[q2.back()]<=a[i])q2.pop_back();
        q2.push_back(i);
        if(i>=k)cout<<a[q2.front()];
    }
    return 0;
}