【每日一题】滑动窗口（单调队列）

滑动窗口时单调队列的经典问题。时间复杂度和空间复杂度都是o（n）。
单调队列即，队列中保存的值是有单调性的。实现原理类似双指针。
用head指针代表对首，tail代表队尾，head > tail 即队列为空。
当窗体大小大于k时，head++，即q[head]+k-1 < i.
当a[i]比队尾若干元素的值更最时，tail--，相当于删除了这若干值，因为这若干值对答案的贡献为0。
单调队列的代码如下：

int head = 0,tail = -1;
for(int i = 1;i <= n; i++)
{
    while(head <= tail && q[head] + k - 1 < i)++head;
    while(head <= tail && a[q[tail]] > a[i])--tail;
    q[++tail] = i;
}

本题code：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+100;
int q[maxn],a[maxn];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i = 1; i <= n; i++)scanf("%d",a+i);
    int head = 0,tail = -1;
    for(int i = 1;i <= n; i++)
    {
        while(head <= tail && q[head] + k - 1 < i)++head;
        while(head <= tail && a[q[tail]] > a[i])--tail;
        q[++tail] = i;
        if(i>=k)printf("%d ",a[q[head]]);
    }
    puts("");
    head = 0,tail = -1;
    for(int i = 1; i <= n; i++)
    {
        while(head <= tail && q[head] + k - 1 < i)++head;
        while(head <= tail && a[q[tail]] < a[i])--tail;
        q[++tail] = i;
        if(i>=k)printf("%d ",a[q[head]]);
    }
    return 0;
}

单调队列可以用deque实现
deque的一些操作
deque<int>q;
q.push_back(w):将w添加到队列的末尾
q.push_front(w):将w添加到队列的前面
q.pop_back() ：将最后一个元素删除
q.pop_front() ：将队列开始一个元素删除</int>

https://ac.nowcoder.com/acm/contest/5667/F

这题是一个二维的单调队列（用deque实现）
还有gcd的递推实现：附上代码：

#include <bits/stdc++.h>
#define ll long long
#define pi pair<int,int>
#define mk make_pair
#define pb push_back
using namespace std;

const int maxn = 5005;
int gd[maxn][maxn];
int a[maxn][maxn];

int main()
{
    for(int i=0;i<maxn;i++)
    for(int j=0;j<maxn;j++)
    {
        if(j == 0)gd[i][j] = j;
        else if(i == 0)gd[i][j] = j;
        else
        {
            if(i >= j)gd[i][j] = gd[i-j][j];
            else gd[i][j] = gd[i][j-i];
        }
    }

    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);

    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        gd[i][j] = i*j/gd[i][j];
    }

    deque<int>q;
    for(int i=1;i<=n;i++)
    {
        while(q.size())q.pop_back();
        for(int j=1;j<=m;j++)
        {
            while(q.size() && q.front() <= j - k)q.pop_front();
            while(q.size() && gd[i][q.back()] < gd[i][j])q.pop_back();
            q.push_back(j);
            a[i][j] = gd[i][q.front()];
        }
    }
    ll ans = 0;
    for(int j=k;j<=m;j++)
    {
        while(q.size())q.pop_back();
        for(int i=1;i<=n;i++)
        {
            while(q.size() && q.front() <= i-k)q.pop_front();
            while(q.size() && a[q.back()][j] < a[i][j])q.pop_back();
            q.push_back(i);
            if(i >= k)ans += a[q.front()][j];
        }
    }
    cout<<ans<<'\n';
    return 0;
}