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

题目：

有一堆数字共N个数字，以及一个大小为k的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

题解：
用单调队列，判断完依次输出队头。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 1;
int a[N];

int main() {
    int n, k;
    cin >> n >> k;
    int m;
    vector<int>v;//单调递减队列
    for (int i = 0; i < n; ++i) {
        cin >> m;
        v.push_back(m);
    }
    vector<int> v_MAX, v_MIN,
        q(v.size(), 0);//放下标
    int x = 0, y = -1;
    for (int i = 0; i < (int)v.size(); ++i) {
        while (x <= y && v[q[y]] > v[i]) {
            --y;
        }
        q[++y] = i;
        if (i - q[x] + 1 > k)  ++x;
        if (i >= k - 1) v_MIN.push_back(v[q[x]]);
    }
    for (int i = 0; i < (int)v_MIN.size(); ++i)
        printf("%d"" ", v_MIN[i]);
    printf("\n");
    q.clear();
    int l = 0, r = -1;
    for (int i = 0; i < (int)v.size(); ++i) {
        while (l <= r && v[q[r]] < v[i]) {
            --r;
        }
        q[++r] = i;
        if (i - q[l] + 1 > k)  ++l;
        if (i >= k - 1) v_MAX.push_back(v[q[l]]);
    }
    for (int i = 0; i < (int)v_MAX.size(); ++i)
        printf("%d"" ", v_MAX[i]);

    return 0;
}