单调栈与单调队列

单调栈

单调栈是满足单调性的栈结构。

举例说明：

当向栈中插入元素时，为了维护栈的单调性（单调递增），需要弹出一些元素，而弹出元素的数目应该是最小的，之后再将元素插入到栈顶。

例如，栈中目前有元素 $\{21,15,7,0\}$，之后我们插入元素 $12$ 则需要依次弹出元素 $0,7$ 此时栈变为 $\{21,15,12\}$。

// 插入元素 x
stack<int> stk;
while (stk.size() && stk.top() <= x) {
	stk.pop();
}
stk.push(x);

洛谷 P5788. 【模板】单调栈

题意：给定长度为 $n$ 的数列 $a$，求每个位置 $i$ 右边第一个大于 $a_i$ 的元素下标 $f(i)$，不存在则 $f(i)=0$。

从右往左扫描，用栈维护"右边可能成为答案的下标"。对当前位置 $i$，不断弹出栈顶对应值 $\le a_i$ 的下标（它们不可能是 $i$ 及更左边位置的答案），剩下的栈顶就是 $f(i)$，最后把 $i$ 入栈。每个元素至多入栈、出栈一次，总复杂度 $O(n)$。

#include <bits/stdc++.h>
using namespace std;

const int N = 3000010;
int a[N], ans[N], stk[N];
int n, top;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = n; i >= 1; i--) {
        while (top && a[stk[top]] <= a[i]) top--;
        ans[i] = top ? stk[top] : 0;
        stk[++top] = i;
    }

    for (int i = 1; i <= n; i++) cout << ans[i] << ' ';

    return 0;
}

单调队列

问题：

给定长度为 $n$ 的整数数组，求每连续 $k$ 个元素中的最大值和最小值？

暴力想法自然是两重循环，枚举每 $i\sim i+k-1$ 的子段，求出其最大值和最小值，时间复杂度为 $O(n\times k)$。当 $k$ 较大时，显然会 TLE。

此时可以使用单调队列。

单调队列指的是队列中的元素满足单调递增或单调递减的性质。

例如我们维护一个单调递增队列 $Q=\{\}$，初始为空，且 $k=3$。

有如下序列：

$213015747307699$

操作如下：

操作	结果
$21$ 入队	$\{21\}$
$30\ge 21$，$30$ 入队	$\{21,30\}$
$15\le 30\mathrm{\&}15\le 21$，$15$ 入队，$30,21$ 出队	$\{15\}$
$7\le 15$， $7$ 入队 $15$ 出队	$\{7\}$
$47\ge 7$，$47$ 入队	$\{7,47\}$
$30\le 47$，$30$ 入队，$47$ 出队	$\{7,30\}$
此时 $7$ 已在窗口外，$7$ 出队，$76\ge 30$，$76$ 入队	$\{30,76\}$
$99\ge 76$，$99$ 入队	$\{30,76,99\}$

总结，单调队列每一次操作遵循以下流程：

1. 第一步从队头开始清理已不在窗口的元素
2. 第二步从队尾开始清理不满足单调性质的元素
3. 第三步将元素入队

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

题意：给定长度为 $n$ 的序列 $a$ 和窗口大小 $k$，窗口从左向右每次滑动一个单位，输出每个窗口内的最小值和最大值。$n\le {10}^6$。

注意：求最小值维护单调递增（不减）队列，求最大值维护单调递减（不增）队列，两者完全对称。每次插入 $a_i$ 前：

1. 弹出队头越界的下标（$q[hh]<i-k+1$）；
2. 弹出队尾不满足单调性的元素；
3. $i$ 入队，当 $i\ge k$ 时队头即为当前窗口的最值。

#include <bits/stdc++.h>
using namespace std;

const int N = 1000010;
int a[N], q[N];
int n, k;

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];

    // 最小值：维护单调递增队列
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i++) {
        if (hh <= tt && q[hh] < i - k + 1) hh++;      // 1. 清理窗口外的队头
        while (hh <= tt && a[q[tt]] >= a[i]) tt--;    // 2. 清理破坏单调性的队尾
        q[++tt] = i;                                  // 3. 入队
        if (i >= k) cout << a[q[hh]] << ' ';
    }
    cout << endl;

    // 最大值：维护单调递减队列
    hh = 0, tt = -1;
    for (int i = 1; i <= n; i++) {
        if (hh <= tt && q[hh] < i - k + 1) hh++;
        while (hh <= tt && a[q[tt]] <= a[i]) tt--;
        q[++tt] = i;
        if (i >= k) cout << a[q[hh]] << ' ';
    }
    cout << endl;

    return 0;
}

队列中每个元素至多入队、出队一次，总复杂度 $O(n)$。

应用：单调队列除了解决滑动窗口最值外，还常用于优化形如 $dp[i]=\underset{i-k\le j<i}{max}(dp[j])+w(i)$ 的 DP 转移，把 $O(nk)$ 优化到 $O(n)$。

习题

1. AcWing 830. 单调栈
2. AcWing 154. 滑动窗口
3. 洛谷 P1440 求 m 区间内的最小值

参考

• OI Wiki：单调栈
• OI Wiki：单调队列