单调栈学习笔记

单调栈是什么

从名字上来看单调栈单调队列十分的相似,同样的它们的具体内容也十分的相似。单调栈本质上是一个,这个栈中的元素是严格有序(即不存在相等元素)的,所以栈顶元素总是比栈里的元素大或小,用公式表达如下:

i[0,n){Stacki+1>Stacki,NGEStacki+1<Stacki,NLE\forall i \in \left[0, n\right) \begin{cases} Stack_{i + 1} > Stack_{i}, & NGE \\ Stack_{i + 1} < Stack_{i}, & NLE \end{cases}

其中 NGE 指的是 Next Greater Element,即下一个比它大的元素,而 NLE 指的是 Next lower Element,即下一个比它小的元素。

单调栈用来干什么

解决 NGE、NLE 问题。

如何维护单调栈

以 NGE 问题为例。

例题:洛谷 P5788 【模板】单调栈

我们需要获取序列中第ii 个元素之后第一个大于aia_{i}的元素的下标,联想到单调栈的性质即使用单调栈解决此题。

我们维护一个栈stack,遍历序列aa 时进行如下操作:

  1. 检查stack是否为空,如果是则将i入栈并进行下一次判断(continue)。
  2. 不断检查stack的栈顶元素(下标)在aa 中的取值并且如果a[i]>a[stack.top]a\left[i\right] > a\left[stack.top\right],就将stack.top的答案设置为i,因为i为下一个比它大的元素。

不难发现,经过以上的维护,栈stack内的元素始终是有序的,所以答案的正确性也就得到了保证。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <stack>

using namespace std;

const uint32_t MAX_N = 3e6 + 10;

uint32_t n;
uint32_t a[MAX_N], ans[MAX_N];
stack<uint32_t> stk;

int main() {
ios::sync_with_stdio(false);

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

for (uint32_t i = 1; i <= n; ++i) {
while (stk.size() && a[stk.top()] < a[i]) {
ans[stk.top()] = i;
stk.pop();
}
stk.push(i);
}

for (uint32_t i = 1; i <= n; ++i) {
cout << ans[i] << ' ';
}
cout << endl;

return 0;
}