Növbəti böyük element

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon Bloomberg
QalaqBaxılıb 19

Növbəti böyük element verdiyimiz bir problemdir array. N dəyəri olan bu sıra (müsbət və ya mənfi ola bilər). Verilən massivdə ilk böyük_elementi sağ tərəfində tapmalıyıq. Daha böyük_element yoxdursa, -1 götürün.

Giriş Formatı

Tək bir tam dəyər N-i ehtiva edən birinci sətir. N tam ədədi ehtiva edən ikinci sətir.

Çıxış formatı

Bir sıra içərisindəki hər bir mağaza üçün növbəti böyük elementi çap edin. Qeyd: Elementin sırası dəyişə bilər.

Məhdudiyyətlər

  • 1 <= N <= 1000000
  • | a [i] | <= 1000000000.
Example Input-1:
9
4 3 6 2 -1 4 -5 3 2
Example Output-1:
3 -> 6
4 -> 6
-1 -> 4
2 -> 4
-5 -> 3
2 -> -1
3 -> -1
4 -> -1
6 -> -1

Explanation: Yığın istifadəsi ilə hər ədədin növbəti böyük elementini tapırıq. Əvvəlcə ilk nömrəni yığına itələyirik. İndi indeks 1-dən n-1-ə qədər qalan bütün dəyərləri təkrarlayın. İndiki indeks olduğumuz dəyər yığının üst hissəsinin dəyərindən kiçik və ya ona bərabərdirsə, onu yığına itələyirik. İndiki indeks olduğumuz dəyər yığının üst hissəsindən daha böyükdürsə. Sonra elementləri yığından çıxarırıq və keçdiyimiz açılmış element üçün növbəti böyük elementi təyin edirik. Yığımın şərti üstü cari elementdən daha çox olan vəziyyəti alana qədər təkrarlayın. Bütün dəyərlər üçün tapın. Daha yaxşı başa düşmək üçün aşağıdakı nümunəyə baxın.

Növbəti böyük elementPin

Növbəti böyük elementPin

Növbəti böyük elementPin

Növbəti böyük elementPin

 

Pin

Pin

Pin

Pin

 

Pin

Pin

Növbəti böyük elementPin

Növbəti böyük elementPin

Növbəti böyük elementPin

Növbəti böyük elementPin

Sonrakı üçün alqoritm daha böyük element

Algorithm:
Step:1 Push the First value of array into a stack.
Step:2 Traverse all the nodes one by one and follow the conditions:
       i) Mark the current element as traverse.
       ii) If the stack is not empty then, compare the top of the stack with the traverse.
           If traverse is greater then pop element from the stack and assigns NGE of pop element as traverse else push traverse into stack. 
       iii) Repeat step 2.i and 2.ii till we traverse all the values of array.
Step:3 The remaining values/elements in the array have no element which is NGE. So, we assign -1 as NGE of all remaining values.
Step:4 Print the NGE values of each node.

Həyata keçirilməsi

/*C++ Implementation of Next greater element problem*/ 
#include<bits/stdc++.h>
using namespace std;
int main() 
{ 
    int n;
    /*take the input n*/
    cin>>n;
    int a[n];
    /*take input array of n numbers*/
    int nge[n];
    /*vector use to store the answer*/
    vector<pair<int ,int > > v;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    stack<int> s;
    /*push first element into sack*/
    s.push(a[0]);
    /*traverse rest of others elements*/
    for(int i=1;i<n;i++)
    {
        /*current element*/
        int traverse=a[i];
        /*element at top of stack*/
        int top=s.top();
        /*if traverse is less than top of stack*/
        if(traverse<top)
        {
            s.push(traverse);
        }
        else/*if traverse is greater than top of stack*/
        {
            /*repeat till traverse greater than top of stack*/
            while(s.size()>0&&s.top()<traverse)
            {
                int x=s.top();
                s.pop();
                v.push_back({x,traverse});
            }
            /*if stack is empty then insert traverse*/
            if(s.size()==0)
            {
                s.push(traverse);
            }
            /*add traverse into stack*/
            if(traverse<s.top())
            {
                s.push(traverse);
            }
        }
    }
    /*after traversing all element we check stack contain values or not. If stack contain some 
    values then pop them one by one and assign NGE as -1 to all elements of stack*/
    while(s.size()>0)
    {
        int x=s.top();
        s.pop();
        v.push_back({x,-1});
    }
    /*print the answer*/
    for(int i=0;i<v.size();i++)
    {
        cout<<v[i].first<<" -> "<<v[i].second<<endl;
    }
    return 0; 
}
Input:
4
12 14 22 4
Output:
12 -> 14
14 -> 22
4 -> -1
22 -> -1

Zamanın mürəkkəbliyi

O (N) çünki bir massivin bütün elementlərini keçirik və əməliyyatı yerinə yetiririk. Vektordan istifadə edərək nəticəni xətti keçid.

Kosmik Mürəkkəblik

O (N) çünki n cüt tam ədədi saxlayan vektordan istifadə edirik ) və N ədədlərini saxlamaq üçün bir sıra.

References

Translate »