参考博客：https://blog.csdn.net/zuzhiang/article/details/78134247
题目大部分都是模板题，代码都差不多，只是有一道题看起来没有那么明显。
我感觉大致规律就是入栈时找到左边第一个元素位置（大于或小于当前元素值），出栈时找到右边第一个元素位置。
如果找左右两边第一个比当前元素小的元素位置，就维护一个单调递增（确切来说是单调不递减）的单调栈。
如果找左右两边第一个比当前元素大的元素位置，就维护一个单调递减（确切来说是单调不递增）的单调栈。
如果找左右两边第一个小于等于当前元素的元素位置，就维护一个单调递增（严格单调递增）的单调栈。
如果找左右两边第一个大于等于当前元素的元素位置，就维护一个单调递减（严格单调递减）的单调栈。
其实也不用记，写单调栈时临时考虑一下就行了
题目一：洛谷P2659
题目链接：https://www.luogu.org/problem/P2659
其实就是找出每一个元素左右两边第一个小于它的元素位置。
因为是左右两边第一个小于它的元素位置，所以我们就维护一个单调不递减的单调栈。
从栈底到栈顶的数字是依次增大的，在求的过程中要始终保持递增（不递减）的性质。我们每次在数字入栈时求出数字左边第一个小于它的数字位置，在出栈的时候求出右边第一个小于它的数字位置，为什么是这样，看下面，我这里的栈保存的是元素下标，而不是元素值。
L[i]记录左边第一个小于a[i]的元素位置（下标），没有就是0，R[i]记录右边第一个小于a[i]的元素位置，没有就是n+1。
对于一个a[i]，假如a[i]大于栈顶元素（我的栈存的是下标，我们比较是就拿这个下标的值比较），那么如果把a[i]压入栈顶，这个栈还是递增的，这个时候栈顶元素就是第一个小于a[i]的数字，我们直接把L[i]赋值为栈顶元素就行了，然后让 i （下标）入栈。
对于a[i]等于栈顶元素的情况，假如说值都是5好吧，那么其实栈顶的5在它入栈的时候，它的L数组值（它左边第一个小于它的元素位置）我们一定会先得到对吧，那么当前的a[i](也是5），它的L数组值肯定等于栈顶元素的L数组值吧，因为他俩相等，所以直接把a[i]的L数组值赋值为栈顶元素的L数组值就可以了，再把 i 入栈。
假如a[i]小于栈顶元素，那么如果我们把a[i]压入栈中，那么这个栈里面的元素就不单调递增了，所以说我们需要把栈里面比a[i]大的元素都弹出，假如现在我们要弹出当前栈顶元素，那么其实现在a[i]就是栈顶元素右边的第一个小于栈顶元素的值，所以我们这个时候可以直接把R[s.top()]赋值为i （出栈时得到右边第一个小于栈顶元素的元素位置），这样每当我们出栈一个元素，这个元素的左右两边第一个小于它的元素位置就都找到了（左边的在进栈时就找到了）。
代码（我的栈都不是手写栈，比较菜）：
#include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<map> #include<stack> #include<cmath> #include<vector> #include<set> #include<cstdio> #include<string> #include<deque> using namespace std; typedef long long LL; #define eps 1e-8 #define INF 0x3f3f3f3f #define maxn 2000005 stack<int>s; int n,m,k,t; int a[maxn]; int L[maxn],R[maxn]; inline int read(){ int f=1,x=0;char ch; do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9'); do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9'); return f*x; } int main() { n=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++){//线性扫一遍 while(!s.empty()&&a[s.top()]>a[i]){//先检查栈顶元素大于a[i]的情况 //保存一下栈顶元素值（下标） R[s.top()]=i; //得到栈顶元素右边第一个小于它的元素下标 s.pop(); //出栈,出栈时就已经的到了R[i],i在这里是s.top() } if(s.empty()) //假如栈为空 L[i]=0; else if(a[s.top()]==a[i]) //假如栈顶元素等于a[i],那么L[i]就赋值为栈顶元素的L数组值 L[i]=L[s.top()]; else //栈顶元素小于a[i]，把a[i]入栈 L[i]=s.top(); s.push(i); //入栈，入栈之前已经得到了L[i] } while(!s.empty()){//最后栈顶可能还有元素没有出栈，这个时候他们的R数组值都是n+1，因为右边没有比他们小的值了 R[s.top()]=n+1; s.pop(); } LL ans=0; for(int i=1;i<=n;i++) ans=max(ans,(LL)a[i]*(R[i]-L[i]-1)); printf("%lld ",ans); return 0; }
类似题目：POJ 2559、POJ2796
题目二：poj 3250
题目链接（poj）：http://poj.org/problem?id=3250
题目链接（vj）：https://vjudge.net/problem/POJ-3250
找每个元素右边第一个大于等于当前元素的值，假设用i表示当前元素位置，R[i]表示右边第一个大于等于a[i]的元素位置，那么开区间 （i，R[i]）里面包含了R[i]-i-1个小于a[i]的元素，将这些个数全部相加输出。
既然是右边第一个大于等于，那么我们在入栈时就直接入栈，反正不用左边的，考虑出栈，什么时候出栈呢，当即将压入的元素大于等于当前栈顶元素就出栈，此时R[s.top()]就赋值为i，也就是栈顶元素得到了右边第一个大于等于它的元素位置，就这样一直出栈，直到栈为空或者栈顶元素大于即将要入栈的元素。考虑到这一点，我们就知道我们要维护的是一个严格单调递减的单调栈了。
代码：
#include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<map> #include<stack> #include<cmath> #include<vector> #include<set> #include<cstdio> #include<string> #include<deque> using namespace std; typedef long long LL; #define eps 1e-8 #define INF 0x3f3f3f3f #define maxn 80005 int a[maxn]; int n,m,k,t; LL ans; int R[maxn];//a[i]右边第一个大于它的元素位置 stack<int>s; int main() { while(scanf("%d",&n)!=EOF){ while(!s.empty()) s.pop(); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++){//维护一个严格单调递减的单调栈 while(!s.empty()&&a[s.top()]<=a[i]){//这里是 a[s.top()]<=a[i]了 R[s.top()]=i; s.pop(); } s.push(i); } while(!s.empty()){ R[s.top()]=n+1; s.pop(); } ans=0; for(int i=1;i<=n;i++) ans+=R[i]-i-1; printf("%lld ",ans); } return 0; }
题目三：POJ3494
题目链接（POJ）：https://vjudge.net/problem/16256/origin
题目链接（vj）：https://vjudge.net/problem/POJ-3494
题意：在给出的矩阵里面找一个最大的子矩阵（里面的元素个数最多），要求子矩阵里面元素都是1，输出这个子矩阵里面的元素1的个数。
这个乍一看不知道还真的不知道要用单调栈，但是既然你都说了用单调栈，强行联想还是很容易想出来的，就是维护2000个单调栈，对于矩阵的每一列（当然，每一行也可以），我们都把它看成一个单调栈。
比如说矩阵 ：
0 1 1 0
1 1 1 0
1 1 1 1
0 1 1 0
我们处理一下就得到了如下矩阵：
0 1 2 0
1 2 3 0
1 2 3 4
0 1 2 0
这里有4列，分别是0 1 1 0、1 2 2 1、2 3 3 2、0 0 4 0
a[i][j]这个时候就表示在第i行第j列位置前面（包含a[i][j]）有多少个连续的数字1。这是左右方向上的连续值，然后我们就要求竖直方向上连续的值了。
对于每一列，我们都找到他上下方向（竖直方向）上第一个小于当前元素的元素位置，然后取a[i][j]*(R[j][i]-L[j][i]-1)中的最大值就行了，这里j代表列，R[j][i]就代表第j列的第i个元素下面第一个小于a[i][j]的元素位置。可能比较绕。
代码（我的代码不是很快）：
#include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<map> #include<stack> #include<cmath> #include<vector> #include<set> #include<cstdio> #include<string> #include<deque> using namespace std; typedef long long LL; #define eps 1e-8 #define INF 0x3f3f3f3f #define maxn 2005 int a[maxn][maxn]; int L[maxn][maxn],R[maxn][maxn];//L[i][j]代表第i列上小于a[j][i]的第一个元素位置(上下方向) int n,m,k,t; stack<int>s[maxn]; LL ans=0; int main() { while(scanf("%d%d",&n,&m)!=EOF){ for(int i=1;i<=m;i++) while(!s[i].empty()) s[i].pop(); for(int i=1;i<=n;i++){ int pre=0;//对矩阵进行处理，pre代表当前j前面的连续1的个数 for(int j=1;j<=m;j++){ scanf("%d",&a[i][j]); if(a[i][j]) //当前元素是1 a[i][j]=++pre; else //当前元素是0，重置pre pre=0; } } for(int j=1;j<=m;j++){//枚举列 for(int i=1;i<=n;i++){//每一列就是一个单调不递减的单调栈 ，s[j]就是第j列的栈 while(!s[j].empty()&&a[s[j].top()][j]>a[i][j]){ //其实就是前面多加了一维 R[j][s[j].top()]=i; s[j].pop(); } if(s[j].empty()) L[j][i]=0; else if(a[i][j]==a[s[j].top()][j]) L[j][i]=L[j][s[j].top()]; else L[j][i]=s[j].top(); s[j].push(i); } while(!s[j].empty()){ R[j][s[j].top()]=n+1; s[j].pop(); } } ans=0; for(int j=1;j<=m;j++){ for(int i=1;i<=n;i++){ ans=max(ans,(LL)a[i][j]*(R[j][i]-L[j][i]-1));//找最大值就行了 } } printf("%lld ",ans); } return 0; }