• 单调队列问题
    a[l],a[l + 1],a[l + 2]....a[r-2],a[r-1],a[r],当这个区间往右移动的时候，只会a[l]离开窗口，a[r + 1]进入窗口，那么我们只需比较这个即可
    典型单调队列题目，我们队列左端存的是当前最优解，当窗口往右移动时，我们看这个队列左端是不是已经不再 k 这个范围内了，如果是的话我们让他出队，然后我们看 a[i] 也就是当前新加的元素 ，如果他比队列中的某些元素小的话，那么他就可能成为后面的最优解，那么我们往前找到一个合适的位置来存储他，也就是他前面的元素都比他小，后面的元素都比他大。
  • 注意队列中存的是他的下标 l = r = 1 开始 ,让第一个元素先进队 注意是 ++ r
    #include<bits/stdc++.h>
#define pr printf
#define sc scanf
#define fur(i,a,b) for(int i = a; i<= b ;i++)
#define fdr(i,a,b) for(int i = a; i>= b ;i--)
using namespace std;
const int N = 1e6 + 5;
int du[N],n ,k ,a[N];
typedef long long ll;
int main()
{
 // freopen("in.txt","r",stdin);
  sc("%d %d",&n ,&k);
  int l = 1 ,r = 1;
  for(int i = 1 ; i <= n ; i ++){
      sc("%d",&a[i]);
  }
  du[l] = 1;
  if(k ==1)pr("%d ",a[1]);
  for(int i = 2 ; i <= n ;i ++){
      if(i - du[l] >= k && l <= r)l++;
      while(l <= r && a[du[r ]] >=a[i]) r--;
      du[++r] = i; // ++ r 是因为他要在队尾插入
      if(i>=k)pr("%d ",a[du[l]]);
  }
  puts("");
  l = 1, r= 1;
  du[l] = 1;
  if(k ==1)pr("%d ",a[1]);
  for(int i = 2 ; i <= n ;i ++){
      if(i - du[l] >= k && l <= r)l++;
      while(l <= r && a[du[r ]] <=a[i]) r--;
      du[++r] = i;
      if(i>=k)pr("%d ",a[du[l]]);
  }
  puts("");
  return 0;
}