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

Правка en1, от 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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Eclosion 2021-01-17 16:50:39 1320
en1 Английский Eclosion 2021-01-17 09:18:31 1421 Initial revision (published)