求连续的k个中最大最小值，k是滑动的，每次滑动一个
用双端队列维护可能的答案值
假设要求最小值，则维护一个单调递增的序列
对一開始的前k个，新增加的假设比队尾的小。则弹出队尾的，直到新增加的比队尾大。增加队尾
从第k+1个到最后一个，依照上述规则，压入新数，然后弹出队首元素（满足队首元素相应原来序列的位置必须在视窗内。否则，继续弹出下一个）
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std; inline void put(int x){
if(x< 0){
putchar('-');
x = -x;
}
if(x == 0){
putchar('0');
return;
}
char s[20];
int bas = 0;
for(;x;x/=10)s[bas++] = x%10+'0';
for(;bas--;)putchar(s[bas]);
return;
} int n,k;
int num[1111111];
int ansmin[1111111];
int pj;
int ansmax[1111111];
int pjj;
struct node
{
int p,v;
}q[1111111];
int main()
{
#ifndef ONLINE_JUDGE
freopen("G:/1.txt","r",stdin);
freopen("G:/2.txt","w",stdout);
#endif
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&num[i]);
}
int start=1,tail=1;
for(int i=1;i<=n;i++)
{
if(i==1)
{
q[1].v=num[1];
q[1].p=1;
}
// for(int j=tail;j>=start;j--)//弹出比它大的数
// {
// if(q[j].v>num[i])
// tail--;
// }
while(tail>=start&&q[tail].v>num[i])
tail--;
q[++tail].v=num[i];
q[tail].p=i;//将该数加到尾巴
//開始输出最小值
if(i>=k)
{
while(i-q[start].p>k-1) start++;
ansmin[pj++]=q[start].v;
}
}
start=1;tail=1;
for(int i=1;i<=n;i++)
{
if(i==1)
{
q[1].v=num[1];
q[1].p=1;
}
// for(int j=tail;j>=start;j--)//弹出比它小的数
// {
// if(q[j].v<num[i])
// tail--;
// }
while(tail>=start&&q[tail].v<num[i])
tail--;
q[++tail].v=num[i];
q[tail].p=i;//将该数加到尾巴
//開始输出最小值
if(i>=k)
{
while(i-q[start].p>k-1) start++;
ansmax[pjj++]=q[start].v;
}
}
for(int i=0;i<pj;i++)
{
put(ansmin[i]);
//printf("%d%c",ansmin[i],i==pj-1?'\n':' ');
putchar(' ');
}
putchar('\n');
for(int i=0;i<pjj;i++)
{
put(ansmax[i]);
//printf("%d%c",ansmax[i],i==pjj-1?'\n':' ');
putchar(' ');
}
putchar('\n');
}