单调栈
单调栈是一种内部元素具有单调性的栈，可以解决求“以某个值为最值的最大区间”等问题。
原理
以下摘自 B3666 求数列所有后缀最大值的位置 - 洛谷 题目描述：
给定一个数列 \(a\)，初始为空。有 \(n\) 次操作，每次在 \(a\) 的末尾添加一个正整数 \(x\)。
每次操作结束后，请你找到当前 \(a\) 所有的后缀最大值的下标（下标从 1 开始）。一个下标 \(i\) 是当前 \(a\) 的后缀最大值下标当且仅当：对于所有的 \(i < j \leq |a|\)，都有 \(a_i > a_j\)，其中 \(|a|\) 表示当前 \(a\) 的元素个数。
考虑用一个栈维护当前数列所有后缀最大值的位置（即下标），初始时栈为空。
易证栈中元素对应的数是单调递减的，因此称为单调栈。
考虑 \(a\) 加入一个元素 \(a_i\) 时单调栈将如何变化。
-
若栈顶元素 \(j\) 满足 \(a_j \le a_i\)，则此时 \(a_j\) 不再是后缀最大值，因此弹出 \(j\)。
-
若栈顶元素 \(j\) 满足 \(a_j > a_i\)，则此时 \(a_j\) 仍然是后缀最大值，不操作。
-
由后缀最大值的定义知 \(a_i\) 一定是后缀最大值，\(i\) 入栈。
由于单调栈中的元素对应的数单调递减，所以应删去的元素仅存在于栈顶，因此只需要重复执行第一步直到 \(a_j > a_i\) 即可。
类似地，单调栈可以维护数列所有后缀最值或前缀最值，这是单调栈维护的本质信息。
实现
使用 STL 的 std::vector 容器而非 std::stack 实现单调栈，原因是 std::stack 时空常数巨大且 std::vector 支持 std::stack 的全部功能。
以下为核心代码：
std::vector<int> s;
for (int i = 1; i <= n; i++)
{
while (!s.empty() && a[s.back()] <= a[i])
s.pop_back();
s.push_back(i);
}
for (auto i : s)
std::cout << i << " ";
std::cout << "\n";
算法分析
每个元素只会在被插入时入栈一次，也只会出栈至多一次，所以总时间复杂度是 \(O(n)\)，均摊单次插入 \(O(1)\)。
基础应用
单调栈可以解决求“以某个值为最值的最大区间”的问题。
以下为 P5788 【模板】单调栈 - 洛谷 题目描述：
给出项数为 \(n\) 的整数数列 \(a_{1 \dots n}\)。
定义函数 \(f(i)\) 代表数列中第 \(i\) 个元素之后第一个大于 \(a_i\) 的元素的下标，即 \(f(i)=\min_{i<j\leq n, a_j > a_i} \{j\}\)。若不存在，则 \(f(i)=0\)。
试求出 \(f(1\dots n)\)。
每一个被弹出的栈顶元素 \(j\) 都满足 \(a_j\) 是区间 \([1, i - 1]\) 中的后缀最大值，因此 \(a_i\) 就是在 \(a_j\) 之后第一个大于 \(a_j\) 的元素。
#include <iostream>
#include <vector>
int a[3000005], ans[3000005];
std::vector<int> s;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int n;
std::cin >> n;
for (int i = 1; i <= n; i++)
std::cin >> a[i];
for (int i = 1; i <= n; i++)
{
while (!s.empty() && a[s.back()] < a[i])
{
ans[s.back()] = i;
s.pop_back();
}
s.push_back(i);
}
for (int i = 1; i <= n; i++)
std::cout << ans[i] << " ";
std::cout << "\n";
return 0;
}
类似地，对于一个数列 \(a\)，单调栈可以在 \(O(n)\) 时间内求出以任意一个 \(a_i\) 为最值的区间位置。
单调队列
单调队列是一种内部元素具有单调性的队列，可以解决求“区间内最值”等问题。
原理
以下摘自 B3667 求区间所有后缀最大值的位置 - 洛谷 题目描述：
给定一个长度为 \(n\) 的数列 \(a\)，对于其中每个长度为 \(k\) 的子区间，请你求出这个这个子区间构成的数列的所有后缀最大值的位置。
后缀最大值的定义同上。
仍考虑单调栈的思想。设当前处理的子区间为 \([l, r]\)，则问题的本质是求 \([1, r]\) 的后缀最大值里落在 \([l, r]\) 的部分。
因此当询问到 \([l, r]\) 时，\([1, l − 1]\) 内的数将不再有价值。这部分数是储存在栈底的，将其删去后栈中的元素就是 \([l, r]\) 的后缀最值了。
栈无法删除底部元素，因此使用双端队列实现，因此这种数据结构被称为单调队列。
类似地，单调队列可以维护数列中所有长度为 \(k\) 的子区间的前缀最值或后缀最值，这是单调队列维护的本质信息。
实现
使用 STL 的 std::deque 容器实现单调队列。但 std::deque 时空常数巨大，必要时应改为手写队列。
以下为核心代码：
std::deque<int> s;
for (int i = 1; i <= n; i++)
{
int l = std::max(i - k + 1, 1);
while (!s.empty() && s.front() < l)
s.pop_front();
while (!s.empty() && a[s.back()] < a[i])
s.pop_back();
s.push_back(i);
if (i >= k)
{
for (auto i : s)
std::cout << i << " ";
std::cout << "\n";
}
}
算法分析
与单调栈类似，每个元素只会在被插入时入队一次，也只会出队至多一次，所以总时间复杂度是 \(O(n)\)，均摊单次插入 \(O(1)\)。
基础应用
单调队列可以解决求“给定长度的区间内最值”的问题。
以下为 P1886 滑动窗口 /【模板】单调队列 - 洛谷 题目简述：
给出项数为 \(n\) 的整数数列 \(a_{1 \dots n}\) 和一个正整数 \(k\)，求 \(a\) 中每个长度为 \(k\) 的子区间中的最大值和最小值。
以最大值为例，单调队列中存储的是每个区间中所有后缀最大值的位置，易证单调队列中元素对应的数单调递减，因此队首对应的即为这个区间的最大值。
#include <iostream>
#include <deque>
#include <algorithm>
int a[1000005];
std::deque<int> s;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int n, k;
std::cin >> n >> k;
for (int i = 1; i <= n; i++)
std::cin >> a[i];
for (int i = 1; i <= n; i++)
{
int l = std::max(i - k + 1, 1);
while (!s.empty() && s.front() < l)
s.pop_front();
while (!s.empty() && a[s.back()] >= a[i])
s.pop_back();
s.push_back(i);
if (i >= k)
std::cout << a[s.front()] << " ";
}
std::cout << "\n";
s.clear();
for (int i = 1; i <= n; i++)
{
int l = std::max(i - k + 1, 1);
while (!s.empty() && s.front() < l)
s.pop_front();
while (!s.empty() && a[s.back()] <= a[i])
s.pop_back();
s.push_back(i);
if (i >= k)
std::cout << a[s.front()] << " ";
}
std::cout << "\n";
return 0;
}