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:

#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;
    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--)
            ans[]=i;// the answer
    while(p>0) ans[st[p]]=0,p--;
    while(!q.empty()) ans[]=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. 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)