Monotone-queue

单调队列

定义

单调队列是指是队列中的元素始终保持着单增或者单减的特性的队列。

其实单调队列不只是做到了排序，还可以实现一个功能：在每次加入或者删除元素时都保持序列里的元素有序，即队首元素始终是最小值或者最大值，这个功能非常重要，单调队列我们就是使用的这个功能。

用单调队列来解决问题，一般都是需要得到当前的某个范围内的最小值或最大值。

实现

单调队列我选择用STL的deque来实现(由于单调队列要多次对队尾元素做处理，所以不能使用queue，虽然我觉得这很不符合队列的原理┭┮﹏┭┮)，假设求解为某数组下标范围[i−k+1,i]的元素的最大或最小值，就可以使用单调队列。

单调队列的实现重点在于对队首、队尾不停的动态检查，然后就是对队列的基本操作了。

1.检查队首：如果队首指向的下标小于等于i-k,即队首的元素已经跑出了k长度即[i−k+1,i]这个区间，那么就要将队首元素弹出来。

2.检查队尾：如果队尾的元素大于要添加的值，如果这个值加上去队列就不会保持单调性，所以要弹出队尾元素，（可能会一直不满足，所以要一直弹出队尾元素）。目的就是保持队首元素一直是最小值，且队列单调。

3.加入队尾元素：在检查队尾发现不符合条件并完成弹出后，在队尾插入新元素。

队头始终最小值（升序排列）

deque<int> que;
for (int i = 1; i <= n; i++) {
    while (!que.empty() && i - k >= que.front()) {
        que.pop_front();
    }
    while (!que.empty() && a[que.back()] >= a[i]) {
        que.pop_back();
    }
    que.push_back(i);
}

队头始终最大值（降序排列）

deque<int> que;
for (int i = 1; i <= n; i++) {
    while (!que.empty() && i - k >= que.front()) {
        que.pop_front();
    }
    while (!que.empty() && a[que.back()] <= a[i]) {
        que.pop_back();
    }
    que.push_back(i);
}

一些小念叨

关于单调队列的运用还有很多，例如斜率优化DP等等。

总而言之，使用单调队列优化DP，那么必会有求i之前某个范围的极值的操作，这类DP的方程通常为：
F[i]=min(F[j]+a[i]:j<i)
a[i]是与j无关的数。

后续补充

单调队列与优先队列的区别：单调队列的长度取决于输入数据的合法性，而优先队列的长度始终与输入数据的数量等同。 而他们的单调性都是单调递减或单调递增。

优先队列其实就是堆的一种应用，所以可以使用STL提供的prioriry_queue来实现，具体见我都另一篇博客中的STL heap模拟：

Cpp_note_4 | Charles’s Castle (charles2530.github.io)

单调栈

定义

单调栈，顾名思义就是栈内元素单调按照递增(递减)顺序排列的栈。（单调栈是一种可以以$ O(n) $的时间复杂度解决类似求对于每一个数 i 左边（或右边）第一个（从 i 开始）比它小（或大）的数的问题的算法）

适用问题：

要知道单调栈的适用于解决什么样的问题，我们首先需要知道单调栈的作用。单调栈分为单调递增栈和单调递减栈，通过使用单调栈我们可以访问到下一个比他大（小）的元素（或者说可以）。也就是说在队列或数组中，我们需要通过比较前后元素的大小关系来解决问题时我们通常使用单调栈。

单调栈主要解决以下问题：

单调递减栈：

①在一个队列中针对每一个元素从它右边寻找第一个比它大的元素
②在一个队列中针对每一个元素从它左边寻找第一个比它大的元素

单调递增栈：

①在一个队列中针对每一个元素从它右边寻找第一个比它小的元素
②在一个队列中针对每一个元素从它左边寻找第一个比它小的元素

具体实现

首先是一段伪代码。

伪代码中的栈顶元素出栈和更新结果可以按实际需求调整顺序。

stack<int> st;
for (遍历这个数组){
    while (栈不为空 && 栈顶元素小于当前元素){
        //栈顶元素出栈;
        //更新结果;
    }
    //当前数据入栈;
}

然后我们以一道模板题来作为事例：

P1950 长方形 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

按照题目含义我们需要使用单调栈算出$ l_i$和 $r_i$ ，分别是 ℎ 中左边第一个（从$ h_i $开始）不大于 $h_i$ 的数和右边第一个（从 $h_i$ 开始）小于 $h_i$ 的数。

按照上文的介绍，我们需要使用单调递增栈。（其实上文中的不大于和小于本质只是$<$和$<=$的区别）

需要注意的是，对于上文中这两种栈的两种用途，可以用正序和倒序遍历数组来实现（即所谓左边和右边寻找），本题比较特殊存储的是相应元素的下标，如果要实现存储对应的值也是同理即可。

for (int i = 1; i <= n; i++) {
    stack<int> s1, s2;
    s1.push(1), s2.push(m);
    for (int low = 2, high = m - 1; low <= m + 1, high >= 0;high--, low++) {
        while (!s1.empty() && dp[i][low] < dp[i][s1.top()]) {
            r[s1.top()] = low;
            s1.pop();
        }
        while (!s2.empty() && dp[i][high] <= dp[i][s2.top()]) {
            l[s2.top()] = high;
            s2.pop();
        }
        s1.push(low), s2.push(high);
    }
}

最后是这道单调栈模板题的AC代码：

folding code

#include <bits/stdc++.h>
using namespace std;
#define M 100007
#define N 1007
#define INF 0x3f3f3f3f
#define mod 1000000007
#define ll long long
#define db double
#define pii pair<int, int>
int dp[N][N];
int l[M], r[M];
int n, m;
ll ans;
int main() {
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            char x;
            cin >> x;
            dp[i][j] = (x == '*') ? 0 : dp[i - 1][j] + 1;
        }
    }
    for (int i = 1; i <= n; i++) {
        stack<int> s1, s2;
        s1.push(1), s2.push(m);
        for (int low = 2, high = m - 1; low <= m + 1, high >= 0;
             high--, low++) {
            while (!s1.empty() && dp[i][low] < dp[i][s1.top()]) {
                r[s1.top()] = low;
                s1.pop();
            }
            while (!s2.empty() && dp[i][high] <= dp[i][s2.top()]) {
                l[s2.top()] = high;
                s2.pop();
            }
            s1.push(low), s2.push(high);
        }
        for (int j = 1; j <= m; j++) {
            ans += (j - l[j]) * (r[j] - j) * dp[i][j];
        }
    }
    cout << ans;
    return 0;
}

友情链接： 数据结构——单调栈

写在最后：虽然大多数单调栈的题目都比单调队列难，但其实单调队列可以实现单调栈的几乎所有操作（只要用STL的deque就可以）！！

模板题

扫描

扫描

题目描述

有一个 $1 \times n$ 的矩阵，有 $n$ 个整数。

现在给你一个可以盖住连续 $k$ 个数的木板。

一开始木板盖住了矩阵的第 $1 \sim k$ 个数，每次将木板向右移动一个单位，直到右端与第 $n$ 个数重合。

每次移动前输出被覆盖住的数字中最大的数是多少。

输入格式

第一行两个整数 $n,k$，表示共有 $n$ 个数，木板可以盖住 $k$ 个数。

第二行 $n$ 个整数，表示矩阵中的元素。

输出格式

共 $n - k + 1$ 行，每行一个整数。

第 $i$ 行表示第 $i \sim i + k - 1$ 个数中最大值是多少。

样例 #1

样例输入 #1

5 3
1 5 3 4 2

样例输出 #1

5
5
4

提示

对于 $20%$ 的数据，$1 \leq k \leq n \leq 10^3$。

对于 $50%$ 的数据，$1 \leq k \leq n \leq 10^4$。

对于 $100%$ 的数据，$1 \leq k \leq n \leq 2 \times 10^6$，矩阵中的元素大小不超过 $10^4$ 并且均为正整数。

AC代码

#include <bits/stdc++.h>
using namespace std;
#define M 2000007
#define N 1007
#define INF 0x3f3f3f3f
#define ll long long
#define db double
int a[M];
int n, k;
deque<int> que;
int main() {
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        while (!que.empty() && i - k >= que.front()) {
            que.pop_front();
        }
        while (!que.empty() && a[que.back()] <= a[i]) {
            que.pop_back();
        }
        que.push_back(i);
        if (i >= k) {
            cout << a[que.front()] << endl;
        }
    }
    return 0;
}