zzoce 🧊
单调栈

单调栈

Thu Oct 03 2024
zzcoe
3 分钟
数据结构与算法 数据结构
367 字

P5788 【模板】单调栈 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)题目大意：统计每个数后第一个大于该数的数字的位置。

思路： 将数看成是人的身高，每个人向后看都只能看到第一个比自己高的人，矮的看不见，后边更高的也看不见（因为视线被挡住了）。

所以从左向右遍历，当遇到第一个人，当他比他前一位的人高时，那么这个矮人的结果就出来了，让他离开，然后这位高人继续向前比较，直到遇到不比他矮的人，立正等待比他高的出现，他就可以离开了。

显然可以用栈实现

CPP
1
2
3
4
5
6
7
8
	mp.push(node (a[1],1));
	for (int i=2;i<=n;i++){
		while (!mp.empty()&&mp.top().x<a[i]){//x是矮人的身高
			f[mp.top().j]=i;//j是矮人的输入顺序
			mp.pop();
		}
		mp.push(node (a[i],i));
	}

例题二#

1.最大区间 - 蓝桥云课 (lanqiao.cn)

CPP
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
#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#define ll long long
using namespace std;
const int MAXN=3e5+5;
struct node {
    ll num,l;
};
stack<node> mp;
ll  a[MAXN],fp[MAXN],dp[MAXN];
int main ()
{
    int n;
    a[0]=-1;
    a[n+1]=-1;
    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>a[i];
    }
    mp.push({a[1],1});
    for (int i=2;i<=n+1;i++){
        while (!mp.empty()&&mp.top().num>a[i]){
            fp[mp.top().l]=i;
            mp.pop();
        }
        mp.push ({a[i],i});
    }
    while (!mp.empty()){
        mp.pop();
    }
    mp.push({a[n],n});
    for (int i=n-1;i>=0;i--){
        while (!mp.empty()&&mp.top().num>a[i]){
            dp[mp.top().l]=i;
            mp.pop();
        }
        mp.push ({a[i],i});
    }
    ll sum=0;
    for (int i=1;i<n;i++){
        sum=max (sum,(fp[i]-dp[i]-1)*a[i]);
    }
    cout<<sum<<endl;
    return 0;
}

例题三、#

P 6198 [EER 1] 单调栈 - 洛谷 | 计算机科学教育新生态 (luogu. Com. Cn)