Блог пользователя Eclosion

Автор Eclosion, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 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 года назад, # ^ |
        Проголосовать: нравится 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 года назад, # ^ |
          Проголосовать: нравится 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:3

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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