单调栈练习题
参考博客：https://blog.****.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; }