单调栈求左右第一个比该数大（小）的位置

单调栈解决的是以某个值为最小（最大）值得最大区间。

这是求左右区间第一个比该数小的区间位置。(数组版本和栈版本）

 

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
const int inf = 0x3f3f3f3f;
int dir[8][2]={{1,0},{0,1},{1,1},{1,-1},{-1,1},{-1,-1},{0,-1},{-1,0}};
#define pi acos(-1)
#define ls rt<<1
#define rs rt<<1|1
#define me0(s) memset(s,0,sizeof(s))
#define me1(s) memset(s,1,sizeof(s))
#define mef(s) memset(s,-1,sizeof(s))
#define meinf(s) memset(s,inf,sizeof(s))
const int N=100005;
inline int read() {
char c=getchar(); int x=0, f=1;
while(c<'0'|c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x*f;
}
ll exgcd(ll a,ll b){
if(b==0) return a;
exgcd(b,a%b);
}
ll q_pow(ll a,ll b,ll mod){
ll anss=1;
while(b){
if(b&1) anss=anss*a%mod;
a=a*a%mod;
b>>=1;
}
return anss;
}
ll q_mul(ll a,ll b,ll mod){
ll anss=0;
while(b){
if(b&1) anss=(anss+a)%mod;
a=(a+a)%mod;
b>>=1;
}
return anss;
}
int n,a[N],ra[N],la[N],sta[N];
void aaaa(stack<ll> s){
for(int i=1;i<=n;i++){
while(s.size()&&a[s.top()]>=a[i]) s.pop();
if(s.size()) ra[i]=s.top()-1;
else ra[i]=n;
s.push(i);
}
while(s.size()) s.pop();
for(int i=n;i>=1;i--){
while(s.size()&&a[s.top()]>=a[i]) s.pop();
if(s.size()) ra[i]=s.top()-1;
else ra[i]=n;
s.push(i);
}
}
int main(int argc, char * argv[])
{
ios::sync_with_stdio(false);
while(cin>>n){
for(int i=1;i<=n;i++) cin>>a[i];
int top=0;
for(int i=1;i<=n;i++){
if(top&&a[sta[top-1]]>=a[i]){
top--;
}
la[i]=(top==0)?0:sta[top-1];
sta[top++]=i;
}
top=0;
for(int i=n;i>=1;i--){
while(top&&a[sta[top-1]]>=a[i]) top--;
ra[i]=(top==0)?(n+1):sta[top-1];
sta[top++]=i;
}
for(int i=1;i<=n;i++){
cout<<la[i]<<" "<<ra[i]<<endl;
}
}
return 0;
}