P1886.md

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

Link

Solution

单调队列板子题，啥都没卡，很舒服

Code

#include <algorithm>
#include <cstring>
#include <deque>
#include <iostream>
#include <string>
using namespace std;

int a[1000010];

int main() {
    deque<int> q;
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < k; i++) {
        while (!q.empty() && a[i] <= a[q.back()]) q.pop_back();
        q.push_back(i);
    }
    cout << a[q.front()] << " ";
    for (int i = k; i < n; i++) {
        while (!q.empty() && a[i] <= a[q.back()]) q.pop_back();
        q.push_back(i);
        while (q.front() <= i - k) q.pop_front();
        cout << a[q.front()] << " ";
    }
    cout << endl;
    q.clear();
    for (int i = 0; i < k; i++) {
        while (!q.empty() && a[i] >= a[q.back()]) q.pop_back();
        q.push_back(i);
    }
    cout << a[q.front()] << " ";
    for (int i = k; i < n; i++) {
        while (!q.empty() && a[i] >= a[q.back()]) q.pop_back();
        q.push_back(i);
        while (q.front() <= i - k) q.pop_front();
        cout << a[q.front()] << " ";
    }
    return 0;
}