求左侧第一个小的数(将注释解开将输出右侧第一个小的数,两个信息能够同时维护)。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
const int N = 1e5 + 10;
int n;
int a[N];
int main()
{
ios::sync_with_stdio(false);
cin >> n;
for(int i = 1;i <= n;i ++ ) cin >> a[i];
stack<int> stk;
int r[N] = {0};
memset(r,-1,sizeof(r));
for(int i = 1;i <= n;i ++ )
{
while(stk.size() && a[stk.top()] >= a[i])
{
r[stk.top()] = i;
stk.pop();
}
if(stk.size()) cout << a[stk.top()] << " ";
else cout << -1 << " ";
stk.push(i);
}
// cout << endl;
// for(int i = 1;i <= n;i ++ ) cout << r[i] << " ";
return 0;
}
求右侧第一个大的数,必须将数据存储起来并逆向判断
#include<bits/stdc++.h>
using namespace std;
const int N = 3e6+10;
int n;
int num[N],ans[N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
scanf("%d",&num[i]);
stack<int> s;
for(int i=n;i>=1;i--)
{
while(!s.empty()&&num[i]>=num[s.top()]) s.pop();
//前面的数大于后面的数
//那么后面的数永远不会被当作第一个右侧大的数数出来
ans[i]=s.empty()?0:s.top();
s.push(i);
}
for(int i=1;i<=n;i++)
printf("%d ",ans[i]);
return 0;
}