本题是单调队列题解的入门，当然也可以使用RMQ 和 线段树，不过速度都没有单调队列那么快。
单调队列难点：
1 如何入列，保存数据 -- 最小单调队列的时候， 所有数都入列一次，在新的数据准备入列的时候，增加判断，如果当前数值小于队尾数值，那么队尾数值就出列。空队列的时候直接入列。
2 保存的数列是什么样的？
举例吧： 1 3 -1 -3 5 3 6 7
构建最小单调队列
第一个数值1的时候，空队列，那么入列，得到： 1
第二个数值3， 因为大于1；那么1不用出列，直接入列，得到： 1 3
第三个数值-1，因为小于3，故此3出列，-1入列，继续判断-1小于1，故此1也出列，剩下队列得到： -1
以此类推……
根据实际情况，本题需要的是K大小端中的最小和最大值，那么就可以记录上各个数值的下标，加以判断。即下标不在需要的判断范围之内的就出来，不过这次是从队列头出列。因为去掉这些下标不合要求的数值之后，队列的头数值依然是最小值，故此是当前答案。
#include<cstdio>
const int MAX_N = 1000001;
int N, K;
int arr[MAX_N];
int qu[MAX_N];
int index[MAX_N];
int ans[MAX_N];
void getMins()
{
int tail = 0, head = 1; //初始化tail<head表示为空列
for (int i = 1; i < K; i++) //初始化单调队列
{
while (tail >= head && qu[tail] >= arr[i]) tail--;
qu[++tail] = arr[i]; //记录可能的答案值
index[tail] = i; //记录额外需要判断的信息
}
for (int i = K; i <= N; i++)
{
while (tail >= head && qu[tail] >= arr[i]) tail--; //不符合条件出列
qu[++tail] = arr[i];
index[tail] = i;
while (index[head] <= i-K) head++;
ans[i-K] = qu[head]; //ans从下标0开始记录
}
}
void getMaxs()
{
int tail = 0, head = 1;
for (int i = 1; i < K; i++) //初始化单调队列
{
while (tail >= head && qu[tail] <= arr[i]) tail--;
qu[++tail] = arr[i];
index[tail] = i;
}
for (int i = K; i <= N; i++)
{
while (tail >= head && qu[tail] <= arr[i]) tail--; //不符合条件出列
qu[++tail] = arr[i];
index[tail] = i;
while (index[head] <= i-K) head++;
ans[i-K] = qu[head]; //ans从下标0开始记录
}
}
int main()
{
while (~scanf("%d %d", &N, &K))
{
for (int i = 1; i <= N; i++) scanf("%d", &arr[i]);
getMins();
for (int i = 0; i <= N-K; i++) printf("%d ", ans[i]);
putchar('\n');
getMaxs();
for (int i = 0; i <= N-K; i++) printf("%d ", ans[i]);
putchar('\n');
}
return 0;
}