单调队列模板 滑动窗口

题目描述

有一个长为 nn 的序列 aa，以及一个大小为 kk 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

例如：

The array is [1,3,-1,-3,5,3,6,7][1,3,−1,−3,5,3,6,7], and k = 3k=3。

输入格式

输入一共有两行，第一行有两个正整数 n,kn,k。 第二行 nn 个整数，表示序列 aa

输出格式

输出共两行，第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值

输入输出样例

输入 #1复制

8 3
1 3 -1 -3 5 3 6 7

输出 #1复制

-1 -3 -3 -3 3 3
3 3 5 5 6 7

说明/提示

【数据范围】
对于 50\%50% 的数据，1 \le n \le 10^51≤n≤105；
对于 100\%100% 的数据，1\le k \le n \le 10^61≤k≤n≤106，a_i \in [-2^{31},2^{31})ai​∈[−231,231)。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
typedef long long ll;
typedef double db;
int all, k;
struct node
{
    int n, m;
} a[maxn];
deque<node> q;
void BIG(int all, int k)
{
    for (int i = 1; i <= all; ++i)
    {
        while (!q.empty() && a[i].m >= q.front().m )q.pop_front(); // 求最小的
        q.push_front(a[i]);
        while (q.back().n <= i - k) q.pop_back();
        if (i >= k) cout<<q.back().m<<" ";
    }
    q.clear();
}
void LOW(int all, int k)
{
    for (int i = 1; i <= all; ++i)
    {
        while (!q.empty() && a[i].m <= q.front().m) q.pop_front(); // 求最大的
        q.push_front(a[i]);
        while (q.back().n <= i - k) q.pop_back();
        if (i >= k) cout<<q.back().m<<" ";
    }
    q.clear();
}
int main()
{
    cin>>all>>k;
    for (int i = 1; i <= all; ++i) cin>>a[i].m, a[i].n = i;
    LOW(all, k);
    cout<<endl;
    BIG(all, k);
    return 0;
}