### Eclosion's blog

By Eclosion, history, 4 months ago, As we all know, the way to find the first element on the left that is larger than the current element, is to use the stack.

This problem can be solved in O(n).

But how to find the second element?

Is there a O(n) solution to this?

I use the stack and the priority queue to solve it in O(nlogn), my code is at the bottom:

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define sz size()
using namespace std;
const int N=1e5+10;
int a[N];
int st[N],ans[N];
struct cmp
{
bool operator()(pair<int,int>a,pair<int,int>b)
{
return a.first>b.first;
}
};
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int p=0;
priority_queue<pair<int,int>,vector<pair<int,int> >,cmp>q;
for(int i=n;i>=1;i--)
{
while(!q.empty()&&q.top().first<a[i])
{
q.pop();
}
while(p>0&&a[st[p]]<a[i])
{
q.push(make_pair(a[st[p]],st[p]));
p--;
}
st[++p]=i;
}
while(p>0) ans[st[p]]=0,p--;
while(!q.empty()) ans[q.top().second]=0,q.pop();
//there is no answer for these element
return 0;
}



If anyone has a better solution, please let me know, i'll be very grateful.

———————————————————————————————————————————————————————————————————————————— Hey guys, this problem is over, i find a O(n) solution to solve this problem, just need to use two stack, but to confirm the stack's monotonicity, i need to reverse it.

Here is my final code for this problem:

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define sz size()
#define pii pair<int,long long>
#define mkp make_pair
using namespace std;
const int N=1e6+10;
stack<int>st1,st2,st3;
int a[N],ans[N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=n;i>=1;i--)
{
while(!st2.empty()&&a[st2.top()]<a[i])//the second stack
{
ans[st2.top()]=i;
st2.pop();
}
while(!st1.empty()&&a[st1.top()]<a[i])
{
st3.push(st1.top());//the third stack just use to reverse the element to confirm the monotonicity
st1.pop();
}
st1.push(i);
while(!st3.empty()) st2.push(st3.top()),st3.pop();//put in the second stack
}
while(!st1.empty()) ans[st1.top()]=0,st1.pop();
while(!st2.empty()) ans[st2.top()]=0,st2.pop();
for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
return 0;
} Comments (8)
 » Can you please explain your code? I think it fails on 5 3 4 2 1. Sorry if I am wrong.
•  » » » I see. Thank you for the explanation. Can you please explain your code? How do you use the priority_queue to find the answer? Thanks!