【学习笔记】单调队列和单调栈

单调栈

以这道题为例：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\)，在栈非空的情况下重复进行以下操作直到不满足条件（以最大值为例，最小值同理）：

1. 令队尾元素为 \(j\)，若 \(a_j \le a_i\) 则弹出 \(j\)
2. 令队首元素为 \(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)\)。