这题高中就做了两遍，感觉理解不是很透彻，今天又做到这题，写一篇题解来加深印象 看题： 
题意不难，现在我来还原一下这题应有的完整思考过程： 本题是要求一个大区间N的每一个连续子区间k的极大（极小）值，为方便理解，先考虑最大值情况
一个很自然的想法便是枚举每一个区间，可以令i从1开始，到n-k结束，在子循环里用j枚举区间元素，每次k都需要从左至右扫描，然后更新出最大值
这个朴素做法正确性没问题，时间复杂度显然是Nk，又因为k，最差时间便是N^2本题中N，需要优化至NlogN或以下级别的时间复杂度，熟悉暴力做法后，我们来考虑优化问题：“
我们用一个队列q来维护当前所在的区间，当窗口向右滑动时，左侧元素出队，右侧元素入队，为了便于理解，我们规定左侧是头，右侧是尾
而当一个元素a[i]进入这个窗口时，我们可以发现：从区间头开始，到a[i]结束，任何比a[i]小的元素都不会成为现在问题的答案，也不会成为接下来问题的答案
这句话有点绕，但是请理解一下，我举个例子： 假设我们所在一个k=5的区间，区间元素分别是10,9,8,4,3,2——现在的答案显然是10，然后窗口向右滑动，10出队，假设新入队元素是6,现在窗口内的元素是9,8,4,3,2,6
我们可以发现，当6进入到这个窗口时，比6小的4,3,2不再可能成为答案，因为从现在开始窗口向右滑动的过程中，答案至少是6，或者比6大
这便是这道题的思想：维护一个单调的队列，控制窗口内的最大值总在队头，当有新元素进入窗口时，从队尾弹出不符合要求的元素（因为他们不会成为答案），来维护队列的单调性，每次查询时，只需输出队头的最大值即可
上面说的还是比较抽象，我们来看一个具体的例子
这是本题的样例，现在k=3的窗口从左侧开始滑动 
此时队列里只有一个元素1，现在窗口继续滑动 
注意！现在元素3要进入队列，我们已经知道，因为1，所以今后的任何时刻，1都不可能成为答案，我们将1出队，让3入队<img alt="file" src="https://blog.cirno.fun/wp-content/uploads/2022/08/image-1661189221183.png"></img>
窗口继续滑动——队列里加入-1，我们让-1入队即可 现在队头元素便是第一个答案——3
接下来窗口继续向右滑动，此时如果1还在队列中，我们需要将他出队，不过此时他已经不在了 -3入队后队列依旧单调，此时队头是第二个答案3 
现在窗口再次滑动，新的元素是5，此时队列中比5小的的3，-1，-3都不可能成为答案了，我们全部弹出，将5入队，并且打印答案5 
剩余滑动同理： 
如果还没有理解，建议手推一遍上面的过程
下面是代码
#include<bits/stdc++.h>
#define P system("pause")
#define E puts("")
using namespace std;
typedef long long ll;
const int N=5e5+10;
int a[N],q[N],head=1,tail=0;
//为了方便判断队头的位置，我们的队列不储存元素的具体值，存元素在数组a[]中的位置（下标）
void initq(){
head=1;tail=0;
}
int main(){
//ios::sync_with_stdio(false);
int n,k;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
initq();//初始化队列
for(int i=1;i<=n;i++){//注意，现在在维护区间最小值，所以答案总是小的在前，队列是单调递增的
if(head<=tail && i-q[head]>=k)
head++;//当队伍不为空且窗口左侧划过队头所在位置时，队头出队
while(head<=tail && a[q[tail]]>=a[i])
tail--; //当队伍不为空且队尾元素大于当前元素，说明这个元素不可能成为答案了，出队
q[++tail]=i;//当前元素入队
if(i<k)//处理窗口还没进入区间的情况，即上面最开始的两张图，此时只维护队列，不输出答案
continue;
printf("%d ",a[q[head]]);
}
E;
initq();
for(int i=1;i<=n;i++){//完全相同
if(head<=tail && i-q[head]>=k)
head++;
while(head<=tail && a[q[tail]]<=a[i])
tail--;
q[++tail]=i;
if(i<k)
continue;
printf("%d ",a[q[head]]);
}
return 0;
}