洛谷-P1886 滑动窗口 /【模板】单调队列

题目描述

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

例如：

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

输入格式

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

输出格式

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

输入输出样例

输入 #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})a**i​∈[−231,231)。

---

#include <bits/stdc++.h>

using namespace std;

vector<int> seq(1000005);
int n, k;
vector<int> small, big;

ostream & operator<<(ostream & os, const vector<int> & v)
{
    int n = v.size();
    for (int i = 0; i < n; ++i) {
        os << v[i];
        if (i != n - 1) os << ' ';
    }
    os << endl;

    return os;
}

void solve()
{
    deque<int> dq;
    //calculate the minimum of the length K
    for (int i = 0; i < n; ++i) {
        if (!dq.empty() && dq.front() == i - k) dq.pop_front();
        while (!dq.empty() && seq[dq.back()] > seq[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= k - 1) small.push_back(seq[dq.front()]);
    }

    dq.clear();
    for (int i = 0; i < n; ++i) {
        if (!dq.empty() && dq.front() == i - k) dq.pop_front();
        while (!dq.empty() && seq[dq.back()] < seq[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= k - 1) big.push_back(seq[dq.front()]);
    }

    cout << small;
    cout << big;
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> k;
    for (int i = 0; i < n; ++i) cin >> seq[i];
    solve();

    return 0;
}

单调队列模板题，和LeetCode 239.Sliding Window Maximum是一个题目。