单调栈
以这道题为例：P5788。我们考虑维护一个单调栈，里面存的是下标，使里面的下标对应的元素从栈顶到栈底是单调上升的。
- 我们从 (nrightarrow 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 的情况下，所以对于时间要求较紧的题目慎用。具体步骤如下：
- 从 (1rightarrow 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) 的区间。这是不是很眼熟？没错，这不就和单调队列的模板题几乎一样吗？
我们在转移 (dp_i) 的时候，可以维护一个 ([i-k,i-1]) 的单调队列记录 ([i-k,i-1]) 区间内的最大值（最小值），直接进行转移即可。这样的时间复杂度就会大大减小，是 (O(n))。
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
