Bir Array Daha Böyük Element

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon alma Bloomberg KuponDuniya Facebook google microsoft Kahin PayU Samsung Snapdeal cuqquldamaq Zoho
Geyim İnformatika QalaqBaxılıb 218

Problem bəyanat

Bir sıra verildikdə, hər bir elementin növbəti böyük elementini array. Əgər həmin element üçün daha böyük element yoxdursa, onda -1-i çap edəcəyik, əks halda həmin elementi çap edəcəyik.

Qeyd: Sonrakı daha böyük element, daha böyük və həmin elementin sağ tərəfində olan elementdir

misal

9
4 5 8 1 3 7 11 13
The next Greater element of 2 is -1
The next greater element of 13 is -1
The next greater element of 11 is 13
The next greater element of 7 is 11
The next greater element of 3 is 7
The next greater element of 1 is 3
The next greater element of 8 is 11
The next greater element of 5 is 8
The next greater element of 4 is 5

Bir Dizidəki Daha Böyük Element üçün yanaşma

Bu problem a qalaq. Burada serialı sondan keçirik və yığında biraz əməliyyat edirik. Ən pis halda, burada yığının ölçüsü N-ə çatır.

Alqoritm

1. Yığın boşdursa və ya cari element yığının üst elementindən daha böyükdürsə, cari elementi yığının üzərinə itələyin və növbəti böyük elementi -1 kimi çap edin.
2. Cari element yığının üst elementindən kiçikdirsə, bunun üçün növbəti böyük element yığının üst elementidir.
3. Yığın boş deyilsə və cari element yığın üst elementindən böyükdür. Yuxarıdakı addımları təkrarlayaraq yığından elementləri açmağa davam edin, başqa bir şey tapılsa daha böyük elementi çap edin -1. Mövcud elementi yığına itələyin
4. 1 və 2-ci addımları massivin başlanğıc indeksinə çatana qədər təkrarlayın.

Həyata keçirilməsi

Bir Dizidəki Daha Böyük Element üçün C ++ Proqramı

#include<bits/stdc++.h>
using namespace std;
void findNGEs(int arr[],int N)
{
  cout << "The next Greater element of "<<arr[N-1] <<" is -1\n";
  
  stack<int> S;
  S.push(arr[N-1]);
  
  for(int i=N-2;i>=0;i--)
  {
    
    while(!S.empty() and arr[i] > S.top()) //If array element is greater than top element then keep i popping
    {
      S.pop();
    }  
    
    if(S.empty()) //if stack is empty means no greater element
      {
        cout<<"The next greater element of "<<arr[i]<<" is -1\n";
        
      }
    else  //if stack not empty then top element is the next greater element
      {
        cout<<"The next greater element of "<<arr[i]<<" is " << S.top()<<"\n";
      }
    S.push(arr[i]);
  }
  
}
int main()
{
   int N;
  cin>>N;
  int arr[N];
  for(int i=0;i<N;i++)
  {
      cin>>arr[i];
  }
  findNGEs(arr,N);
  return 0;
}

Bir Array Next Greater Element üçün Java Proqramı

import java.util.Scanner;
import java.util.Stack;
class sum
{
    public static void findNGEs(int arr[],int N)
    {
      System.out.print("The next Greater element of "+arr[N-1] +" is -1\n");
      Stack<Integer> S = new Stack<Integer>();
      S.push(arr[N-1]);
      for(int i=N-2;i>=0;i--)
      {
        while(!S.empty() && (arr[i] > (int) S.peek())) //If array element is greater than top element then keep i popping
        {
          S.pop();
        }  
        if(S.empty()) //if stack is empty means no greater element
        {
            System.out.print("The next greater element of "+arr[i]+" is -1\n");
        }
        else  //if stack not empty then top element is the next greater element
        {
            System.out.print("The next greater element of "+arr[i]+" is " + (int) S.peek()+"\n");
        }
        S.push(arr[i]);
      }
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        findNGEs(a,n);
    }
}
5
3 5 1 7 2
The next Greater element of 2 is -1
The next greater element of 7 is -1
The next greater element of 1 is 7
The next greater element of 5 is 7
The next greater element of 3 is 5

Bir Dizidəki Daha Böyük Element üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (N) burada n - massivdə mövcud olan elementlərin sayı. Burada sıra dəyərini tam bir dəfə ziyarət edirik. Bu yanaşma bizi xətti zaman mürəkkəbliyinə aparır.

Kosmik Mürəkkəblik

O (N) çünki yığının maksimum ölçüsü O (n) səviyyəsinə qalxır.

References

Translate »