单调栈专题训练

简介

一、定义

单调栈是一种高效，方便，简单的数据结构，其特点与单调队列类似，满足在栈里的数据呈现单调递增或者递减的特性，用来计算一定区间的值。

二、原理

(1)当新元素在单调性上优于栈顶时（单增栈新元素比栈顶大，单减栈新元素比栈顶小），压栈，栈深+1；

(2)当新元素在单调性与栈顶相同（新元素于栈顶相同）或劣于栈顶时（单增栈新元素比栈顶小，单减栈新元素比栈顶大），弹栈，栈深-1；

(3)根据题目条件计算栈变动后的最优值。

三、实现形式

STL的stack库，数组+栈顶指针

四、几点注意

数据类型$long long$，建议$scanf$不要漏掉$lld$。
注意栈空的情况，此时无法取栈顶元素或者弹栈。
注意旧元素的延展性和新元素的继承性。

例题

洛谷 P3467 海报PLA

基本思路

当新元素与栈内某元素相同时，海报可以共用，因此海报数-1,。于是我们只需计算，若高度不同的时候，海报数+1，若相同，则海报数不变，其他遵守单调栈规则。

 1 #include<bits/stdc++.h>
 2 #define FOR(i,a,b) for(int i=a;i<b;i++)
 3 #define FOR2(i,a,b) for(int i=a;i<=b;i++)
 4 #define ll long long
 5 #define INF  0x7f7f7f7f;
 6 #define MAXN 2600100
 7 #define MOD 10007
 8 using namespace std;
 9 ll arr[MAXN];
10 ll n,ans=0;
11 stack<ll>s;
12 int main()
13 {
14     cin>>n;
15     FOR(i,0,n)
16     {
17         ll w;cin>>w>>arr[i];
18         while(!s.empty()&&s.top()>=arr[i])
19         {
20             if(s.top()!=arr[i])
21             {
22                 ans++;
23             }
24             s.pop();
25         }
26         s.push(arr[i]);
27     }
28     cout<<ans+s.size()<<endl;
29     return 0;
30 }

View Code

洛谷 SP1805 HISTOGRA - Largest Rectangle in a Histogram

基本思路

每一列记录三个元素，当前高度$h$，左边扩展的最远的列数$l$，右边扩展最远的列数$r$。

当一个新元素要入栈时，若新元素$h$>栈顶$h$，则栈内元素的右边界扩展到等于新元素所在列（站内元素$h$均小于新元素$h$）；

若新元素$h$<=栈顶$h$，则栈顶元素出栈，记录此时最大值，和栈顶元素的右边界$rr$；出栈后新的栈顶元素的右边界扩展到$rr$，计算此时最大值，直到栈顶元素$h$小于新元素$h$。

举个栗子：n=7 , 2 1 4 5 1 3 3

红色为即将弹出栈，深蓝色为已经出栈的元素，最后要插入一个虚矩形，使栈内元素全部出栈，计算最优值。

AC代码如下

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<stack>
 4 #include<algorithm>
 5 #define FOR(i,a,b) for(int i=a;i<b;i++)
 6 #define FOR2(i,a,b) for(int i=a;i<=b;i++)
 7 #define ll long long
 8 #define INF  0x7f7f7f7f;
 9 #define MAXN 100100
10 #define MOD 10007
11 using namespace std;
12 typedef struct{
13     ll l,r,w;
14 }NODE;NODE nodes[MAXN];
15 ll arr[MAXN];
16 ll n,ans=0;
17 int main()
18 {
19     while(cin>>n){
20     if(n==0)break;
21     stack<NODE>s;;ans=0;
22     FOR(i,0,n)
23     {
24         scanf("%lld",&nodes[i].w);
25         nodes[i].l=nodes[i].r=i;
26     }
27     nodes[n]={n,n,0};
28     FOR2(i,0,n)
29     {
30         while(!s.empty()&&s.top().w>=nodes[i].w)
31         {
32             ans=max(ans,s.top().w*(s.top().r-s.top().l+1));
33             nodes[i].l=s.top().l;//新元素继承出栈元素的延展性 
34             ll rr=s.top().r; 
35             s.pop();
36             if(!s.empty())
37             {//仍在栈中的元素获得延展性，计算最大值 
38                 s.top().r=rr;
39             }
40         }
41         if(!s.empty())ans=max(ans,s.top().w*(s.top().r-s.top().l+1));
42         s.push(nodes[i]);
43     }
44     printf("%lld
",ans);
45     }
46     
47     return 0;
48 }

View Code

相关应用

最长上升子序列

[洛谷P1823]音乐会的等待

基本思路

此题不需要考虑元素的延展性，只需要考虑身高相等的情况，记录连续相等的人数，并累加即可

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<stack>
 4 #include<algorithm>
 5 #define FOR(i,a,b) for(int i=a;i<b;i++)
 6 #define FOR2(i,a,b) for(int i=a;i<=b;i++)
 7 #define ll long long
 8 #define INF  0x7f7f7f7f;
 9 #define MAXN 500100
10 #define MOD 10007
11 using namespace std;
12 typedef struct{
13     ll w,sam;
14 }NODE;NODE arr[MAXN];
15 ll n,ans=0;
16 stack<NODE>s;
17 int main()
18 {
19     scanf("%lld",&n);
20     FOR(i,0,n){
21         scanf("%lld",&arr[i].w);arr[i].sam=1;//自己与自己相等 
22         if(s.empty()){
23             s.push(arr[i]);continue;
24         }
25         while(!s.empty()&&s.top().w<=arr[i].w)
26         {
27             if(s.top().w==arr[i].w)
28             {//若相等则都能见面 
29                 arr[i].sam+=s.top().sam;
30             } 
31             ans+=s.top().sam;
32             s.pop();
33         }
34         if(!s.empty())ans++;
35         s.push(arr[i]);
36     }
37     cout<<ans<<endl;
38     return 0;
39 }

View Code

[洛谷P4147&BZOJ 3039]玉蟾宫

基本思路

此题可用悬线法和单调栈解决。

若用单调栈，则对每一行进行处理，表示向上延伸的高度，即$a[i][j]=ch=='F'?a[i-1][j]+1:0;$

注意末尾需要放置虚矩阵，然后逐行扫描，与SP1805 单调栈做法类似，考虑元素的延展性和单调性。

 1 #include<bits/stdc++.h>
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<stack>
 5 #include<algorithm>
 6 #define FOR(i,a,b) for(int i=a;i<b;i++)
 7 #define FOR2(i,a,b) for(int i=a;i<=b;i++)
 8 #define ll long long
 9 #define INF  0x7f7f7f7f;
10 #define MAXN 2000
11 #define MOD 10007
12 using namespace std;
13 typedef struct{
14     int w,h;
15 }NODE;
16 int n,m,arr[MAXN][MAXN];
17 NODE dp[MAXN][MAXN];
18 int main()
19 {
20 //    freopen("t1.in","r",stdin);
21     cin>>n>>m;
22     FOR2(i,1,n)
23         FOR2(j,1,m)
24         {
25             char ch;
26             cin>>ch;while(ch==' '||ch=='
')cin>>ch;
27             dp[i][j].h=ch=='R'?0:dp[i-1][j].h+1;
28         }
29     FOR2(i,1,n)dp[i][m+1].h=0;
30     int ans=0;
31     FOR2(i,1,n)
32     {
33         stack<NODE>s;
34         FOR2(j,1,m+1)
35         {
36             int temp=0;dp[i][j].w=1;
37             while(!s.empty()&&s.top().h>=dp[i][j].h)
38             {//使用temp记录比s.top().h小的元素通过延展可以获得的最大值 
39                 temp+=s.top().w;
40                 s.pop(); 
41                 if(!s.empty())ans=max(ans,s.top().h*(temp+s.top().w));
42             }
43             s.push(dp[i][j]);
44             s.top().w+=temp;//继承比dp[i][j]大的元素的延展性 
45             ans=max(ans,s.top().h*s.top().w);
46         }
47     }
48     cout<<ans*3<<endl;
49     
50     return 0;
51 }

View Code

单调栈 专题训练

简介

一、定义

二、原理

三、实现形式

四、几点注意

例题

洛谷 P3467 海报PLA

基本思路

洛谷 SP1805 HISTOGRA - Largest Rectangle in a Histogram

基本思路

相关应用

最长上升子序列

[洛谷P1823]音乐会的等待

基本思路

[洛谷P4147&BZOJ 3039]玉蟾宫

基本思路

单调栈专题训练