单调队列

主要用于解决滑动窗口类问题的数据结构(在求窗口最大值时只需要 $O (n)$ 比树状数组/线段树块得多)

void solve() {
    int n, k;cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];

    deque<int> maxq, minq;

    for (int i = 1;i <= n;i++) {
	    //若最新要入的数字比前一个的小，则将前一个去掉，以此类推，然后再入新下标
        while (!minq.empty() && a[i] <= a[minq.back()])
            minq.pop_back();
        minq.push_back(i);

        if (i >= k) {
        //若前面的数字已经和当前的数字下标差距超过k了，则没用了，可以直接去掉了
            while (!minq.empty() && minq.front() < i - k + 1)
                minq.pop_front();
            cout << a[minq.front()] << ' ';
        }
    }
    cout << '\n';

    for (int i = 1;i <= n;i++) {
        while (!maxq.empty() && a[i] >= a[maxq.back()])
            maxq.pop_back();
        maxq.push_back(i);

        if (i >= k) {
            while (!maxq.empty() && maxq.front() < i - k + 1)
                maxq.pop_front();
            cout << a[maxq.front()] << ' ';
        }
    }
    cout << '\n';
}

deque<int> Q; // 存储的是编号
for (int i = 0; i < n; ++i)
{
    if (!Q.empty() && i - Q.front() >= m) // 毕业
        Q.pop_front();
    while (!Q.empty() && V[Q.back()] < V[i]) // 比新生弱的当场退役（求区间最小值把这里改成>即可）
        Q.pop_back();
    Q.push_back(i); // 新生入队
    if (i >= m - 1)
        cout << V[Q.front()] << " ";
}

单调队列通常和 DP/二分等等算法一起出现。

ST 表/单调队列

P2216 [HAOI2007] 理想的正方形 - 洛谷 | 计算机科学教育新生态

单调队列优化 DP

P2034 选择数字 - 洛谷 | 计算机科学教育新生态

P2627 [USACO11OPEN] Mowing the Lawn G - 洛谷 | 计算机科学教育新生态

(待更 $\dots$ )