单调队列定义

维护一个队列，能像队尾存入最新的数据，也能从队首读取最旧的数据。同时，可以快速访问队列中的最大值或最小值。

即队首或队尾始终是队列中的最值。

核心：得到当前某个范围内的最小值或最大值。

实现

保证队首的元素为队列中的最值，不妨令队首元素为最小值。若新加入的值小于队首，则入队；否则，弹出队首元素知道队首元素小于新加入的值。

用法

修改于 9-4
最近单调队列的题目做的多，总结一下用法和注意点：

• 当你需要维护一个带有长度限制的单调区间来获取区间的某一最值
• 此队列为双向队列，可以使用 deque，只能从队尾入队，可从队尾出队使队内数据为最优，长度限制导致的出队从队首出去
• 在队内存储数据的下标

单调栈

与单调队列类似，使用数据结构的基本操作维护一个单调区间。

二者实现起来均相当加单，但是在做优化时很多问题具有一定的思维难度。

用法

修改于 9-4
最近单调栈的题目做的多，总结一下用法和注意点：

• 找出后面第一个比自己大/小的值

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

#include <algorithm>
#include <deque>  //双向队列
#include <iostream>
#define ll long long
using namespace std;

int n, k;
ll a[1000005];
deque<ll> q;  // 一个队列依次只能维护一种最值

int main() {
    ios::sync_with_stdio(0);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;

    // 维护最小值
    for (int i = 1; i <= n; i++) {  // i代表队尾下标
        cin >> a[i];
        while (!q.empty() && a[i] < a[q.back()])
            q.pop_back();
        q.push_back(i);
        if (q.front() < i - k + 1)
            q.pop_front();
        if (i >= k)
            cout << a[q.front()] << ' ';
    }
    cout << endl;
    q.clear();
    // 维护最大值
    for (int i = 1; i <= n; i++) {
        while (!q.empty() && a[i] > a[q.back()])
            q.pop_back();
        q.push_back(i);
        if (q.front() < i - k + 1)
            q.pop_front();
        if (i >= k)
            cout << a[q.front()] << ' ';
    }
    return 0;
}