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])↵
{↵
ans[q.top().second]=i;// the answer↵
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;↵
}↵
↵
~~~~~↵
↵
Sorry to waste your time.
↵
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])↵
{↵
ans[q.top().second]=i;// the answer↵
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;↵
}↵
↵
~~~~~↵
↵
Sorry to waste your time.
