• 涉及知识点：队列/双指针

  • 做法：我看大佬们都是写的优先队列，我这里讲一下deque（双端队列）的解法吧，原理都是一样，首先先看一下deque的写法：

    deque<int> q;//定义双端队列
q.push_front(x);//队列头部插入元素x
q.push_back(x);//队列尾部插入元素x
q.front();//引用最前面的元素
q.back();//引用最后面的元素
q.pop_front();//删除队列最前面的元素
q.pop_back();//删除队列最后面的元素
q.size();//返回双端队列大小

    对于题目，我们要维护一个deque区间的最大值以及最小值，我们讲一下维护最小值的方法：
    维护deque，每次入队要先和队首元素的位置相比较，如果距离大于k，则队首元素不断出队，然后和队尾元素大小比较，如果队尾元素大于等于当前值，则队尾元素不断出队，最后将当前位置放到队尾，则最后的队首元素就是区间最小值，维护最大值类似

  • 代码：
    #include <bits/stdc++.h>
using namespace std;
#define ll  long long
const int maxn = 1e6 + 5;
int a[maxn];
deque<int> q1,q2;
int main()
{
  int n,k;
  scanf("%d%d",&n,&k);
  for(int i=1;i<=n;i++)scanf("%d",&a[i]);
  for(int i=1;i<=n;i++){
      while(q1.size()>0 && i-q1.front()>=k)q1.pop_front();
      while(q1.size()>0 && a[q1.back()]>=a[i])q1.pop_back();
      q1.push_back(i);
      if(i>=k)
          printf("%d ",a[q1.front()]);
  }
  printf("\n");
  for(int i=1;i<=n;i++){
      while(q2.size()>0 && i-q2.front()>=k)q2.pop_front();
      while(q2.size()>0 && a[q2.back()]<=a[i])q2.pop_back();
      q2.push_back(i);
      if(i>=k)
          printf("%d ",a[q2.front()]);
  }
  return 0;
}