滑动窗口--单调队列！

单调队列

解决大小为k的区间的最值问题，区别于RMQ和线段树的是，单调队列允许移动k区间，时间复杂度O(n)

滑动窗口

给定一个大小为n≤1e6的数组。有一个大小为k的滑动窗口，它从数组的最左边移动到最右边。

您只能在窗口中看到k个数字。每次滑动窗口向右移动一个位置。

以下是一个例子：

该数组为[1 3 -1 -3 5 3 6 7]，k为3。

求出每个k大小区间的最大值和最小值。
思路：维护队列的单调性，往队尾插入元素之前，先将队尾大于等于当前数的元素全部弹出即可；
这样所有数均只进队一次，出队一次，时间复杂度是 O(n)的

代码（双端队列）

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define pb push_back
#define sc(a) scanf("%d",&a)
#define scl(a) scanf("%lld",&a)
#define scs(a) scanf("%s",a+1)
#define pf printf
const int mod=1e9+7;
const int N=1e6+10;
struct node
{
    int v,id;
}a[N];
int n,k;
deque<node>q1,q2;
int main()
{
    //3 1 -3 2 3 4 -1 5 4
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i].v,a[i].id=i;
    for(int i=1;i<=k;i++)
    {
        if(q1.empty())q1.push_back(a[i]);
        else {
            while(!q1.empty()&&q1.back().v>a[i].v)q1.pop_back();
            q1.push_back(a[i]);
        }
    }
    cout<<q1.front().v<<" ";
    for(int i=k+1;i<=n;i++)
    {
        while(!q1.empty()&&q1.front().id<i-k+1)q1.pop_front();
        while(!q1.empty()&&q1.back().v>a[i].v)q1.pop_back();
        q1.push_back(a[i]);
        cout<<q1.front().v<<" ";
    }
    cout<<endl;
    for(int i=1;i<=k;i++)
    {
        if(q2.empty())q2.push_back(a[i]);
        else {
            while(!q2.empty()&&q2.back().v<a[i].v)q2.pop_back();
            q2.push_back(a[i]);
        }
    }
    cout<<q2.front().v<<" ";
    for(int i=k+1;i<=n;i++)
    {
        while(!q2.empty()&&q2.front().id<i-k+1)q2.pop_front();
        while(!q2.empty()&&q2.back().v<a[i].v)q2.pop_back();
        q2.push_back(a[i]);
        cout<<q2.front().v<<" ";
    }
    return 0;
}