【单调栈讲授】

 单调栈引入

我们需要维护一个递增的单调栈，同时要给下标入栈，而不是元素入栈。
给i位置入栈的时候，发现右指针i+1位置元素一定小，而左指针i-1位置元素也一定小，所以当前i位置元素出栈对应的答案为（(i+1)指向的下标的元素 - (i-1)指向的下标的元素 - 1）*a[i的下标]
元素：2  1  5  6  2  3  
下标：0  1  2  3  4  5
2入栈
栈：0
1入栈，发现不但调，0下标需要出栈，又因为0已经最左边位置了，所以0的左边应该是-1下标：更新答案{1-（-1）-1}*a[0]=2
栈：1
5入栈
栈：1,2
6入栈
栈：1,2,3
2入栈，发现不但调，3下标需要出栈，所以更新答案：{4-2-1}*a[3]=6，2下标也需要出栈，更新答案：{4-1-1}*a[2]=10
栈：1,4
3入栈
栈：1,4,5
开始出栈：
5下标先出栈，更新答案：{6-4-1}*a[5]=3，4下标再出栈，更新答案：{6-3-1}*a[4]=4，1下标再出栈，更新答案：{6-(-1)-1}*a[1]=6
综上：答案为10.
下面是图解： 

实在这个是一个二维单调栈的用法，再进一步说就是上面的题的二维形态。
请看下图： 

加入如今是这种状态，那么我们可以从第一行开始跑一次一维单调栈，获得一个ans。
然后从第二行跑一次一维单调栈，再获得一个ans，不断的重复，获得最大的ans即可。 

1. #include <bits/stdc++.h>
2. using namespace std;
3. const int N=1e3+5;
4. int n,m,a[N][N],ans;
5. char ch;
6. int maxx(int x){
7.         int ret=0;
8.         stack<int>s;
9.         s.push(0);
10.         for(int i=1;i<=m+1;i++){
11.                 while(a[x][i]<a[x][s.top()]){
12.                         int h=a[x][s.top()];
13.                         s.pop();
14.                         int w=i-s.top()-1;
15.                         ret=max(ret,w*h);
16.                 }
17.                 s.push(i);
18.         }
19.         return ret;
20. }
21. int main(){
22.         cin>>n>>m;
23.         for(int i=1;i<=n;i++){
24.                 for(int j=1;j<=m;j++){
25.                         cin>>ch;
26.                         if(ch=='G')a[i][j]=1;
27.                 }
28.         }
29.         for(int i=1;i<=n;i++){
30.                 for(int j=1;j<=m;j++){
31.                         if(a[i][j])a[i][j]+=a[i-1][j];
32.                 }
33.         }
34.         for(int i=1;i<=n;i++){
35.                 ans=max(ans,maxx(i));
36.         }
37.         cout<<ans*10;
38. }

复制代码

单调栈。为什么能想到单调栈？因为我们要把往后看转化成向左看，即在每个元素入栈的时候看一下左边有几个元素可以看到它。也就是看一下左边有几个元素比它大。
所以我们需要一个单减的单调栈。
新元素进栈时候不会改变单调性就直接进栈，同时统计有几个元素可以看到它（栈里有几个元素）。如果会改变单调性，就把栈中的元素一个一个出栈。统计答案，新元素入栈。

1. #include <bits/stdc++.h>
2. using namespace std;
3. typedef long long ll;
4. ll n,num,sum;
5. stack<int>sk;
6. int main(){
7.         cin>>n;
8.         for(int i=1;i<=n;i++){
9.                 scanf("%lld",&num);
10.                 while(!sk.empty()&&sk.top()<=num) sk.pop();
11.                 sum+=sk.size();
12.                 sk.push(num);
13.                
14.         }
15.         cout<<sum;
16. }

复制代码

首先就是观察规律：

根据2,3环境。
我们发现如果左右有同高度且中间是凸出的矩形条，最好就要把这个赤色横线下面的大矩形给贴一下。
而对于左右有同高度且中间有凹下的矩形条，你按不按照这个赤色横线去贴，答案都稳定。
然后用4环境来举行验证，发现确实是这样的。
那么如何统计答案呢？第2种环境下一定会少贴一次，那么如果有更多同高度的矩形条，就会少贴更多次。我们只需要统计少贴多少次就行。
所以我们需要一个单调增加的栈。
新元素进栈不会改变单调性就直接入栈
新元素入栈会改变单调性，就把栈里面的元素举行出栈，直到左边的同高度的元素也出栈，然后ans++，表示这里可以少贴一次。新元素入栈。

1. #include <bits/stdc++.h>
2. using namespace std;
3. typedef long long ll;
4. int n,ans,d,w;
5. stack<int>sk;
6. int main(){
7.         cin>>n;
8.         for(int i=1;i<=n;i++){
9.                 cin>>d>>w;
10.                 while(!sk.empty()&&w<=sk.top()){
11.                         if(sk.top()==w) ans++;
12.                 sk.pop();}
13.                 sk.push(w);
14.         }
15.         cout<<n-ans;
16. }

复制代码

我们要维护一个单调递增的单调栈，在新来的元素比栈顶元素小的时候，栈顶元素出栈，并更新，直到新元素可以入栈为止。
唯一要注意的就是负数取模了，要现加上去mod再取模。 

1. #include <bits/stdc++.h>
2. using namespace std;
3. typedef long long ll;
4. const int mod=99887765,N=5e6+5;
5. stack<int>st;
6. ll ans;
7. int n,x,a[N],b[N];
8. int main(){
9.         cin>>n>>x;
10.         for(int i=1;i<=n+1;i++){
11.                 cin>>a[i];
12.                 while(!st.empty()&&a[i]<a[st.top()]){
13.                         b[st.top()]=a[i];
14.                         st.pop();
15.                 }
16.                 st.push(i);
17.         }
18.         for(int i=1;i<=n+1;i++){
19.                 ans=ans*x+b[i];
20.                 ans=(ans%mod+mod)%mod;//注意负数是如何取模的
21.         }
22.         cout<<ans;
23. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。