前置知识

简介

单调队列是用于解决滑动窗口类问题的数据结构，即在一个长度为 $n$ 的序列中求连续 $k$ 个数字中的最值问题，单调队列时间复杂度为 $O(n)$ ，这比「ST表」与「线段树」算法更优化。

更广泛地，在以下两种情况时，可以考虑使用单调队列优化。

1. 状态转移方程形如 $dp_i=\min_{0\le j \lt i} \{dp_j+f[j]\}$ 。在这种情况下，下界不变，$i$ 增加 $1$ 时， $j$ 的上界也增加 $1$ ，决策的候选集合只扩大、不缩小。
2. 状态转移方程形如 $dp_i=\min_{i-a\le j \le i-b} \{dp_j+f_i\}$ 。在这种情况下， $i$ 增加 $1$ 时， $j$ 的上界也增加 $1$ ，在一个新的决策加入候选集时，需要把过时的（前面一个超过区间的）决策从候选集合中删掉。滑动窗口问题就是该类型的模板。

原理

对于滑动窗口类问题而言，存在一种暴力解决方法，即从序列的第一个数字枚举，每次求出其后连续 $k$ 个数字中的最值，这种方法的时间复杂度为 $O(nk)$ 如果 $n$ 或 $k$ 的值稍大，就会超时。

而单调队列解决了这个问题，将时间复杂度大大优化，其原理是利用「双端队列」，队列中存放的数字是单调的，其在原序列对应的位置也是单调的。当我们枚举到原序列的第i位时，双端队列中存放的数字就是在区间[i-k+1,i]（此时第i个数字已经被放入）内所有可能成为最值的数字。

现在，我们先求出最小值，因为队列内是单调的，所以队头元素即为该区间内的最小值，当我们要将一个数字加入到队列中时，先判断队尾元素是否大于要加入的数字，如果是的话就队尾元素弹出，直到队尾元素小于要加入的数字，因为该元素不可能成再成为之后区间的最小值，其次还需判断对头元素否已经不在该区间的范围内，如果不在，也将其弹出，最后把原序列中的数字加入队尾，此时，队列中的元素依旧是单调的。下面以一组数据举例。首先规定 $n=8,k=3$ 原始序列为 $1,3,-1,-3,5,3,6,7$。

最终得到答案序列为 $-1,-3,-3,-3,3,3$ 。

参考代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
using namespace Fast; //内容见文章《代码模板》
struct Node{
    int num,p;
}a[1000010];
int n,k,ans[2][1000010];
deque<Node>q;
int main(){
    read(n,k);
    for(int i=1;i<=n;i++){
        a[i].p=i;
        read(a[i].num);
    }
    for(int i=1;i<=n;i++){
        while(!q.empty()&&a[i].num<=q.back().num)
            q.pop_back();
        q.push_back(a[i]);
        while(i-k>=q.front().p)
            q.pop_front();
        ans[0][i]=q.front().num;
    }
    q.clear();
    for(int i=1;i<=n;i++){
        while(!q.empty()&&a[i].num>=q.back().num)
            q.pop_back();
        q.push_back(a[i]);
        while(i-k>=q.front().p)
            q.pop_front();
        ans[1][i]=q.front().num;
    }
    for(int i=k;i<=n;i++){
        print(ans[0][i]);
        space;
    }
    enter;
    for(int i=k;i<=n;i++){
        print(ans[1][i]);
        space;
    }
    return 0;
}