嗯...
题目链接：https://www.luogu.org/problem/P1886
首先这道题很典型，是标准的单调队列的模板题（也有人说单调队列只能解决这一个问题）。这道题可以手写一个队列，也可以用STL中的双端队列...
核心思路：如果一个人比你强并且比你小，那么你无法超过他...
我们把区间最大值和最小值分开求，下面讲解最大值，最小值则反之：
如果队列中有元素并且这个元素比要插入的元素大，即这个人比你强还比你小，那么你永远不能比他强，所以就让你出队，然后让那个人入队。接着处理“退役”的人，如果这个人虽然曾在队列中，但是不在现在的窗口中，那么也把它从队首弹出。
最后注意初始化队列为空和输出...
AC代码：
1 #include2 #include 3 4 using namespace std; 5 const int maxn = 1e6 + 5; 6 int n, k, head, tail, a[maxn]; 7 8 struct node{ 9 int id, val;10 } q[maxn];11 12 inline void work_min(){13 head = 1; tail = 0;14 for(int i = 1; i <= n; i++){15 while(head <= tail && a[i] <= q[tail].val) tail--;16 q[++tail].id = i;17 q[tail].val = a[i];18 while(q[head].id <= i - k) head++;19 if(i >= k) printf("%d ", q[head].val);20 }21 printf("\n");22 }23 24 inline void work_max(){25 head = 1; tail = 0;//初始化 26 for(int i = 1; i <= n; i++){27 while(head <= tail && a[i] >= q[tail].val) tail--;//比你小比你强 28 q[++tail].id = i;29 q[tail].val = a[i];30 while(q[head].id <= i - k) head++;//退役 31 if(i >= k) printf("%d ", q[head].val);//输出 32 }33 printf("\n");34 }35 36 int main(){37 scanf("%d%d", &n, &k);38 for(int i = 1; i <= n; i++) scanf("%d", &a[i]);39 work_min();40 work_max();41 return 0;42 }