How to find the second element on the left that is larger than the current element?

Revision en1, by Eclosion, 2021-01-17 09:18:31

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Eclosion 2021-01-17 16:50:39 1320
en1 English Eclosion 2021-01-17 09:18:31 1421 Initial revision (published)