Eclosion's blog

By Eclosion, history, 4 years ago, In English

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.

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Consider this test:

    3

    2 3 1

    For 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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you please explain your code? I think it fails on 5 3 4 2 1. Sorry if I am wrong.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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:3

        The 1 and 2 's answer is 3, but 2 can't be output.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Eclosion (previous revision, new revision, compare).