单调栈
以这道题为例：P5788。我们考虑维护一个单调栈，里面存的是下标，使里面的下标对应的元素从栈顶到栈底是单调上升的。
- 我们从 \(n\rightarrow 1\) 枚举 \(a_i\)
- 对于每个 \(i\)，如果栈非空，令栈顶的下标为 \(j\)，若 \(a_j\) 不比 \(a_i\) 大，那么这个栈顶元素由于值又小，位置又靠后，如果 \(j\) 能满足的条件，\(i\) 也一定能满足，而且 \(i\) 适用范围更广，所以 \(j\) 不可能成为之后的的 \(f_i\)，所以就将这个元素弹出。
- 重复以上操作直至 \(a_j > a_i\)，此时的栈顶就是 \(f_i\)。其实这也能解释为什么不符合元素的栈顶要出栈：如果不出的话它作为 \(f_i\) 就不满足条件了。这时再把 \(i\) 压入栈中。
其实这个的原理在生活中就已经有了：某个人比你小，又比你厉害，你就永远也找不过他了（一般情况下）。这便是单调栈的基本做法了。
考虑时间复杂度：由于每个元素最多进栈出栈一次，所以时间复杂度应该是 \(O(n)\)。
这道题的代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 3000005;
int a[N], f[N];
stack<int>p;
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = n; i >= 1; i--)
{
while (!p.empty() && a[p.top()] <= a[i]) p.pop();
if (!p.empty()) f[i] = p.top();
else f[i] = 0;
p.push(i);
}
for (int i = 1; i <= n; i++)
printf("%d ", f[i]);
return 0;
}
写代码要注意的几点：
- 枚举栈顶时得用
while而不是if - 如果 \(f_i\) 不存在时栈为空，得特判并将 \(f_i\) 赋值为 \(0\)
其实，单调栈的运用不止如此，我们知道，\(f_i\) 为在第 \(i\) 个元素之后第一个大于 \(a_i\) 的元素下标，也就是说，在 \([i,f_i-1]\) 这个区间内的最大值为 \(a_i\)，同理，我们令 \(g_i\) 为在 \(i\) 之前最后大于 \(a_i\) 的下标，则 \([g_i+1,i]\) 区间的最大值也为 \(i\)，这样可得：\([g_i+1,f_i-1]\) 是以 \(a_i\) 为最大值的最长区间。所以，单调栈解决的问题是：求以 \(x\) 为最值的最长区间。
单调队列
接下来来看单调队列。同样有一道例题：P1886。先考虑维护一个队列（若求最大值则从大到小，若求最小值则从小到大），队尾元素同单调栈类似处理，而最值是在队首。那么特定长度又怎么维护呢？
可以直到，对于一个队首，如果它是在区间外的，则不能作为最值，得弹出，这种操作是可以用双端队列 deque 来实现的。但注意，deque 的常数大，尤其是在未开 O2 的情况下，所以对于时间要求较紧的题目慎用。具体步骤如下：
- 从 \(1\rightarrow n\) 枚举 \(i\)
- 对于每个 \(i\)，在栈非空的情况下重复进行以下操作直到不满足条件（以最大值为例，最小值同理）：
- 令队尾元素为 \(j\)，若 \(a_j \le a_i\) 则弹出 \(j\)
- 令队首元素为 \(j'\)，若 \(j'<i-k+1\)（超出范围）则弹出 \(j'\)
- 将 \(i\) 从末尾进队，令队首元素为 \(s\)，此时 \([i-k+1,i]\) 区间的最大值就是 \(a_{s}\)。
代码如下（deque 实现）：
#include <bits/stdc++.h>
using namespace std;
namespace {
const int N = 1000005;
int a[N];
deque <int> p, q;
int f1[N], f2[N];
void main()
{
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
{
while (!p.empty() && p.front() < i - k + 1) p.pop_front();
while (!p.empty() && a[p.back()] <= a[i]) p.pop_back();
p.push_back(i);
f1[i] = a[p.front()];
while (!q.empty() && q.front() < i - k + 1) q.pop_front();
while (!q.empty() && a[q.back()] >= a[i]) q.pop_back();
q.push_back(i);
f2[i] = a[q.front()];
}
for (int i = k; i <= n; i++) cout << f2[i] << " ";
cout << endl;
for (int i = k; i <= n; i++) cout << f1[i] << " ";
}
}
int main()
{
return 0;
}
注意事项：
- 同样得用
while而不是if - 在记录 \(f_i\) 时得先将 \(i\) 入队
单调队列优化dp
有的时候，dp 的复杂度太高了，在一些特殊的 dp 时，我们就可以用单调队列来优化它。
对于这样的 dp(或者是取 min):
便可以用单调队列优化。
正常情况下，我们需要用两重循环，一重枚举 \(i\)，一重枚举 \(j\) 来进行转移，复杂度是 \(O(n^2)\)。但观察到，对于每个 \(i\)，我们发现，它的转移范围是一个长度为 \(k\) 的区间。这是不是很眼熟？没错，这不就和单调队列的模板题几乎一样吗？文章来源：https://www.toymoban.com/news/detail-612719.html
我们在转移 \(dp_i\) 的时候，可以维护一个 \([i-k,i-1]\) 的单调队列记录 \([i-k,i-1]\) 区间内的最大值（最小值），直接进行转移即可。这样的时间复杂度就会大大减小，是 \(O(n)\)。文章来源地址https://www.toymoban.com/news/detail-612719.html
到了这里，关于【学习笔记】单调队列和单调栈的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
