ቀጣይ ታላቅ ንጥረ ነገር በድርድር ውስጥ


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን ፓም ብሉምበርግ ኩፖንዱኒያ ፌስቡክ google የ Microsoft በ Oracle PayU ሳምሰንግ Snapdeal ትዊተር ቮሆ
ሰልፍ Informatica ክምር

የችግሩ መግለጫ

አንድ ድርድር ከተሰጠ ፣ የእያንዳንዱ ንጥረ ነገር ቀጣይ ትልቁን ንጥረ ነገር በ ውስጥ እናገኛለን ደርድር. ለዚያ ንጥረ ነገር ከዚህ ቀጥሎ የሚበልጥ ንጥረ ነገር ከሌለ ከዚያ -1 ን እናተምበታለን ፣ አለበለዚያ ያንን ንጥረ ነገር እናተምበታለን።

ማስታወሻ: የሚቀጥለው ትልቁ ንጥረ ነገር የበለጠ እና በዚያ ንጥረ ነገር በቀኝ በኩል ያለው ንጥረ ነገር ነው

ለምሳሌ

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

ለቀጣይ ታላቁ አካል አቀራረብ በአድርባይነት

ይህ ችግር ሊፈታ የሚችለው ሀ ቁልል. እዚህ ድርድርን ከጫፍ እናቋርጣለን እና በመደራረብ ላይ የተወሰነ ክዋኔ እናከናውናለን ፡፡ በጣም በከፋ ሁኔታ ፣ እዚህ የተቆለለው መጠን እስከ N. ድረስ ይደርሳል ፡፡

አልጎሪዝም

1. ቁልል ባዶ ከሆነ ወይም የወቅቱ ንጥረ ነገር ከተደራራቢው የላይኛው ንጥረ ነገር የበለጠ ከሆነ ፣ የአሁኑን ንጥረ ነገር በክምችቱ ላይ ይግፉት እና የሚቀጥለውን ትልቁን ንጥረ-ነገር እንደ -1 ያትሙ።
2. የአሁኑ ንጥረ ነገር ከተደራራቢው የላይኛው ንጥረ ነገር ያነሰ ከሆነ ፣ ለዚህ ​​የሚቀጥለው ትልቁ ንጥረ ነገር የቁልል የላይኛው ንጥረ ነገር ነው።
3. ቁልል ባዶ ባይሆንም እና የአሁኑ ንጥረ ነገር ከተደራራቢው የላይኛው ንጥረ ነገር ይበልጣል። ከደረጃው ብቅ ያሉ ክፍሎችን ብቅ ማለቱን ይቀጥሉ ከላይ ያሉትን እርከኖች (ኢተራዎች) ማድረግ ፣ ከሌላው ደግሞ ትልቁን አካል ያትሙ ማተም -1። የአሁኑን ንጥረ ነገር ወደ ቁልል ላይ ይግፉት
4. የድርድሩ ጅምር መረጃ ጠቋሚ እስኪደርስ ድረስ ደረጃ 1 እና 2 ን ይድገሙ።

አፈጻጸም

ለቀጣይ ታላቅ ንጥረ ነገር C ++ ፕሮግራም በአንድ ድርድር ውስጥ

#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;
}

ለቀጣይ ታላቅ ንጥረ ነገር የጃቫ ፕሮግራም በአንድ ድርድር ውስጥ

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

በድርድር ውስጥ ለቀጣይ ታላቁ ንጥረ ነገር ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (ኤን) በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት የት ነው። እዚህ የአንድ ጊዜ ዋጋን በትክክል አንድ ጊዜ እንጎበኛለን። ይህ አካሄድ ወደ መስመራዊ የጊዜ ውስብስብነት ይመራናል ፡፡

የቦታ ውስብስብነት

ኦ (ኤን) ምክንያቱም የቁልል ከፍተኛው መጠን ወደ O (n) ይወጣል።

ማጣቀሻዎች