### 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;
}



• +8

 » 4 months ago, # |   0 Second greatest element is the 2nd element from top of decreasing stack. If you use a vector to in place of a stack, you can easily access 2nd element from end if it exists. Please correct me if I'm wrong.
•  » » 4 months ago, # ^ |   0 Consider this test:32 3 1For 1, the second element greater to the left is 2, however 2 will be popped from the stack when 3 is added. By the time we reach 1, the stack only has one element.
 » 4 months ago, # |   0 Can you please explain your code? I think it fails on 5 3 4 2 1. Sorry if I am wrong.
•  » » 4 months ago, # ^ |   0 For my code, the answer is [0,0,0,2,3], it's the index of the answer.For the fifth element'1', 2 and 4 are larger than it, and 4 is the second, so anwer is 4's index.For the fourth element'2', 4 and 3 are larger than it, and 3 is the second.
•  » » » 4 months ago, # ^ |   0 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!
•  » » » » 4 months ago, # ^ |   0 I use the priority_queue because i need the smallest element is in the queue's front, that make all element smaller than a_i can be outed put.If i use other data structure like vector, i'll happlen the problem like:vector:[1,3,2]ai:3The 1 and 2 's answer is 3, but 2 can't be output.
•  » » 4 months ago, # ^ |   0 For my code, when a element is output from the stack, it mean that have a element larger than it, so i put it in the queue, when it output from the queue, it mean that have the second element larger than it.
 » 4 months ago, # |   0 Auto comment: topic has been updated by Eclosion (previous revision, new revision, compare).