【洛谷P1886】滑动窗口【单调队列】

题目大意：

题目链接：https://www.luogu.org/problemnew/show/P1886
给出n,m$n,m$和一个含有n$n$个元素的数列，求每个连续的长度为m$m$的子串的最小值和最大值。

---

思路：

暴力O(N2)$O(N^2)$，可以用单调队列优化。
每次维护两个单调队列，保证答案就是maxn.front()$maxn.front()$和minn.front()$minn.front()$，并及时将早来的踢掉，后来的入队。时间复杂度O(n)$O(n)$。

---

代码：

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;

deque<int> minn;
deque<int> maxn;
int n,m,a[1000001],ans_min[1000001],ans_max[1000001];

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        while (minn.size()&&a[minn.back()]>a[i]) minn.pop_back();
        while (maxn.size()&&a[maxn.back()]<a[i]) maxn.pop_back();  //维护，保持单调
        minn.push_back(i);
        maxn.push_back(i);  //入队
        if (i>=m)
        {
            while (i-m>=minn.front()) minn.pop_front();
            while (i-m>=maxn.front()) maxn.pop_front();  //踢掉早来的（窗口右移）
            ans_min[i-m+1]=a[minn.front()];
            ans_max[i-m+1]=a[maxn.front()];  //记录答案
        }
    }
    for (int i=1;i<=n-m+1;i++)
     printf("%d ",ans_min[i]);
    printf("\n");
    for (int i=1;i<=n-m+1;i++)
     printf("%d ",ans_max[i]);
    return 0;
}