Monotone Stack
中文名：单调栈
顾名思义，首先是一个栈，然后栈内元素都是单调递增/单调递减的序列。
单调栈的应用并不很广泛，类似单调队列，但在解决某一类问题中，具有出其不意的效果，因为查询的复杂度是在$O(1)$范围内~
而这一类问题具有代表性的就是Next Greater Number,即下一个更大元素.
问题描述：给你一个序列$a$，返回一个等长的数组$ans$， 对应索引存储着下一个更大元素，如果没有更大的元素，则存储$-1$即可。
例如:
$a:[2, 1, 2, 4, 3]$
$ans:[4, 2, 4, 1, 1]$
第一种方式，我们可以采取一种暴力解法，时间复杂度$O(n^2)$，显然，对$n$较小时可以通过。
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
36
37
38
39
40
|
#include <bits/stdc++.h>
#define IOS {ios::sync_with_stdio(false);cin.tie(0);}
#define ll long long
#define PLL pair<ll, ll>
#define SZ(X) (int)X.size()
#define INF 0x3f3f3f3f
using namespace std;
const int maxn =1e5 + 5;
int n;
ll a[maxn], b[maxn];
int main()
{
IOS
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
for(int i = 1; i <= n; i++) {
for(int j = i; j <= n; j++) {
if(a[j] > a[i]) {
b[i] = j;
break;
} else {
b[i] = 0;
}
}
}
for(int i = 1; i <= n; i++) {
cout << b[i] << " ";
}
cout << endl;
system("pause");
return 0;
}
|
第二种方式，我们考虑，把每一个数字想成每一个人，然后值就是这个人的身高，然后我们可以发现：对于某一个人，下一个更大的元素就是第一个露出的人的下标/高度。
于是进栈元素从栈顶到栈底按照升序排列，形成单调的栈。
while的作用是将两个高个子人之间的人全都在栈内删除，因为他们不可能成为Next Greater Number.
单调栈模板
1
2
3
4
5
6
7
8
9
10
11
12
| vector <int> nextGreaterElement(vector <int>& nums) {
vector <int> ans(nums.size());
stack <int> s;
for(int i = num.size() - 1; i >= 0; i--) {
while(!s.empty() && s.top() <= a[i]) {
s.pop();
}
ans[i] = s.empty() ? 0 : s.top();
s.push(ans[i]);
}
return ans;
}
|
我们要从后往前扫描，因为是栈结构，倒着入栈，正着出栈
分析时间复杂度：
如果我们单纯看，那么有一个for和while嵌套，时间复杂度会是$O(n^2)$,但实际上，这个单调栈的时间复杂度是$O(n)$.
我们从整体分析，对于$n$个元素，对于每一个元素，都被push入栈一次，最多会被pop出栈一次，没有额外操作，所以复杂度是和输入成正比的 $O(n)$
例题：如题，写出每一个比当前大的下一个更大数字。
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
36
37
38
39
40
41
42
43
44
|
#include <bits/stdc++.h>
#define IOS {ios::sync_with_stdio(false);cin.tie(0);}
#define ll long long
#define PLL pair<ll, ll>
#define SZ(X) (int)X.size()
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 1e4 + 5;
int n;
ll a[maxn];
ll ans[maxn];
stack <ll> s;
int main()
{
IOS
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
for(int i = n; i >= 1; i--) {
while(!s.empty() && s.top() <= a[i]) {
cout << "stack's element1:" << s.top() << endl;
s.pop();
}
ans[i] = s.empty() ? 0 : s.top();
s.push(a[i]);
cout << "stack's elelment2:" << s.top() << endl;
}
for(int i = 1; i <= n; i++) {
cout << ans[i] << endl;
}
system("pause");
return 0;
}
|
变形:记录每一个比当前大的下一个更大数字的下标和距离。
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
#include <bits/stdc++.h>
#define IOS {ios::sync_with_stdio(false);cin.tie(0);}
#define ll long long
#define PLL pair<ll, ll>
#define SZ(X) (int)X.size()
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 1e4 +5;
int n;
ll a[maxn], ans[maxn];
stack <ll> s;
int main()
{
IOS
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
for(int i = n; i >= 1; i--) {
while(!s.empty() && a[s.top()] <= a[i]) {
s.pop();
}
ans[i] = s.empty() ? 0 : s.top();
s.push(i);
}
for(int i = 1; i <= n; i++) {
cout << ans[i] << " ";
}
cout << endl;
return 0;
}
#include <bits/stdc++.h>
#define IOS {ios::sync_with_stdio(false);cin.tie(0);}
#define ll long long
#define PLL pair<ll, ll>
#define SZ(X) (int)X.size()
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 1e4 +5;
int n;
ll a[maxn], ans[maxn];
stack <ll> s;
int main()
{
IOS
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
for(int i = n; i >= 1; i--) {
while(!s.empty() && a[s.top()] <= a[i]) {
s.pop();
}
ans[i] = s.empty() ? 0 : s.top() - i;
s.push(i);
}
for(int i = 1; i <= n; i++) {
cout << ans[i] << " ";
}
cout << endl;
system("pause");
return 0;
}
|
循环数组
同样是Next Greater Number问题，现在给定的数组是一个环形数组。
例:
$a[i] = [3, 2, 6, 1, 1, 2]$ $ans[6, 6, 0, 2, 2, 3]$
对于环形数组，我们可以想象成原数组在结束的时候，重新拼接了一个新的原数组，这样就形成了环形数组，然后通过取模$%$操作获得元素。
然后我们可以用原数组的2倍开始比较，注意下边从$0$开始，元素要进行取模$%$运算。
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
36
37
38
39
|
#include <bits/stdc++.h>
#define IOS {ios::sync_with_stdio(false);cin.tie(0);}
#define ll long long
#define PLL pair<ll, ll>
#define SZ(X) (int)X.size()
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 1e4 +5;
int n;
ll a[maxn], ans[maxn];
stack <ll> s;
int main()
{
IOS
cin >> n;
for(int i = 0; i < n; i++) {
cin >> a[i];
}
for(int i = 2 * n - 1; i >= 0; i--) {
while(!s.empty() && s.top() <= a[i % n]) {
s.pop();
}
ans[i % n] = s.empty() ? 0 : s.top();
s.push(a[i % n]);
}
for(int i = 0; i < n; i++) {
cout << ans[i] << " ";
}
cout << endl;
system("pause");
return 0;
}
|
