每日一题 单调队列

如果用一般的思路每次查找O(k)的复杂度，总时间复杂度达到O(k(n-k)) 数据范围显然需要优化算法
所以选用易理解的单调队列，和普通队列不同的是，要进行两端删除和插入需要双指针，当然stl的deque（双端队列）就可以实现。

具体实现：比如说[2,1]这个序列，当1一直存在时，2在出窗口之前永远不可能成为最小的那个值，所以这个元素就是无用值，所以每次移动窗口删除队首元素，从右到左寻找单调队列中比刚入队元素大的值（因为刚入队那个元素值始终比他们小，所以最小值就不是这些值）

最大值反之亦然
例如有序列5，2，6，8，10
k = 3
滑动窗口 [5,2,6],8,3 --> 5,[2,6,8],3 --> 5,2,[6,8,3]
单调队列依次为 [2,6 ] [2,6,8] [2,3]

#include <bits/stdc++.h>
#define ll long long int
using namespace std;
const ll maxn=1000010;
ll q1[maxn];///储存位置
ll p1[maxn];///储存min队列
ll q2[maxn];
ll p2[maxn];
ll front=1;///头指针
ll rear=0;///尾指针
ll n,k;
ll a[maxn];
int main()
{
  cin>>n>>k;
  for (int i=1;i<=n;++i)
    cin>>a[i];

  for (int j=1;j<=n;++j)   //min
  {
    while (front<=rear&&q1[rear]>=a[j])///无用值出队
      --rear;
    q1[++rear]=a[j];///入队
    p1[rear]=j;///保存入队值的位置
    while (p1[front]<=j-k)++front;///滑动
    if (j>=k)
      cout<<q1[front]<<' ';
  }
  cout<<endl;
  front=1;
  rear=0;
  for (int j=1;j<=n;++j)//max
  {
    while (front<=rear&&q2[rear]<=a[j])///无用值出队
      --rear;
    q2[++rear]=a[j];///入队
    p2[rear]=j;
    while (p2[front]<=j-k)++front;
    if (j>=k)
      cout<<q2[front]<<' ';
  }
  cout<<endl;
  return 0;
}