单调队列-求区间最值

解决区间尾部固定的RMQ (Range Minimum/Maximum Query)问题，维护滑动窗口中的最值。

RMQ(x, y) 就是询问数组[x, y]区间内部的最小值。

入队操作：

队尾入队，会把之前破坏单调性的元素都从队尾移出（维护单调性）。

出队操作：

如果队首元素超出区间范围，就将元素从队首移出。

元素性质：

队首元素，永远是当前维护区间的（最大/最小）值。

序列中的每一个元素，在依次入队的过程中，每个元素是递减/递增的。

通过代码加深理解：

题目描述
​  给出一个长度为 N 的数组，一个长为 K 的滑动窗口从最左移动到最右，每次窗口移动，如下图：

  找出窗口在各个位置时的极大值和极小值。
输入
  第一行两个数 N, K。
​  第二行有 N 个数，表示数组中的元素。
输出
  输出两行，第一行为窗口在各个位置时的极小值，第二行为窗口在各个位置时的极大值。
样例输入
8 3 
1 3 -1 -3 5 3 6 7
样例输出
-1 -3 -3 -3 3 3
3 3 5 5 6 7
数据规模与约定
  时间限制：1 s
​  内存限制：256 M
​  100% 的数据保证 1≤𝑁≤300000

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <vector>
using namespace std;

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