单调栈

单调栈是指栈内的元素单调递增或者递减,主要是以$O(n)$的时间解决NGE问题(Next Greater Element)。就是在每个元素中,找到下一个比他大的1数。(或者其他的变式)。

img

可以类似于身高,2只能看到4是第一高的,1只能看到2是第一高的…同理。

这一过程,我们可以从后往前面扫描,给出源代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
const int N = 5000100;
int a[N], res[N], n;
stack<int> s;

int main() {
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();
if(!s.empty()) res[i] = s.top();
else res[i] = 0;;
s.push(i);
}
for(int i = 1; i <= n; i++) cout << res[i] << " ";
}

思想就是,比如从最后的3开始。一开始3进栈,然后指向4的时候,因为4比栈顶的值大,那就说明4的右边没有比她大的数,所以3出来4进去。接下来就是2,因为2比栈顶的值4小,所以这个时候2的右边第一个大的数就是4,存储4,并且2进栈。。。以此类推,就能得到序列了。

Author

InverseDa

Posted on

2021-03-14

Updated on

2023-03-30

Licensed under

Comments

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×