सर्वात जवळचे डावे आणि उजवे लहान घटक यांच्यात जास्तीत जास्त फरक शोधा


अडचण पातळी सोपे
वारंवार विचारले फोरकाइट्स
अरे स्टॅक

समस्या विधान

दिले एक अॅरे a [] आकाराचे एन. “जवळच्या डाव्या आणि उजव्या छोट्या घटकांमध्ये जास्तीत जास्त फरक शोधा” ही समस्या आम्हाला एक कार्य तयार करण्यास सांगते. डावीकडील जवळच्या लहान घटकाचे आणि डावीकडील सर्वात जवळचे लहान घटक अनुक्रमे प्रतिनिधित्व करणारे डावे [] आणि उजवे [] असे दोन अ‍ॅरे तयार करतात. मग बाकीच्या अ‍ॅरे मधील अधिकतम फरकांचा अधिकतम शोधा [i] - उजवीकडे [i].

सर्वात जवळचे डावे आणि उजवे लहान घटक यांच्यात जास्तीत जास्त फरक शोधा

उदाहरण

a[ ] = {2, 1, 8}
1
a[ ] = {2, 4, 8, 7, 7, 9, 3}
4

सर्वात जवळचे डावे आणि उजवे लहान घटक यांच्यात जास्तीत जास्त फरक शोधण्यासाठी अल्गोरिदम

  1. आरंभ करणे एक अॅरे अ [] आकाराचे एन.
  2. अ‍ॅरेचे डावे आणि उजवे साठी लहान घटक शोधण्यासाठी फंक्शन तयार करा जे अ‍ॅरे स्वीकारतात, त्याचे आकार आणि आकारमान लहान घटक संचयित करण्यासाठी अ‍ॅरे.
  3. तयार स्टॅक पूर्णांक प्रकारांची डेटा रचना.
  4. अ‍ॅरे ए [] मधून जा. स्टॅक रिक्त नसल्यास आणि स्टॅकच्या शीर्षस्थानी असलेले घटक वर्तमान निर्देशांकातील अ‍ॅरे ए मधील घटकांपेक्षा मोठे किंवा समान असले तरी त्या घटकाला स्टॅकच्या टीपीवर पॉप करा.
  5. स्टॅक रिक्त नाही का ते तपासा, स्टॅकच्या शीर्षस्थानी घटक म्हणून लहान घटकांसाठी अ‍ॅरेमधील वर्तमान निर्देशांकातील मूल्य अद्यतनित करा. अन्यथा लहान घटकांसाठी अ‍ॅरेमधील वर्तमान निर्देशांकातील मूल्य 0 म्हणून अद्यतनित करा.
  6. स्टॅकमधील अ‍ॅरे अ [] मध्ये वर्तमान निर्देशांकावरील मूल्य ढकलणे / घाला.
  7. त्याचप्रमाणे जास्तीत जास्त फरक शोधण्यासाठी आणखी एक फंक्शन तयार करा जे अ‍ॅरे स्वीकारते आणि त्याचे पॅरामीटर आकार आहे.
  8. डावीकडील सर्वात जवळचा लहान घटक संचयित करण्यासाठी आकार एनचा डावा अ‍ॅरे [] तयार करा. दिलेल्या अ‍ॅरेसह लहान घटकांसाठी फंक्शन कॉल करा, त्याचे आकार आहे, आणि पॅरामीटर असल्यामुळे डावे अ‍ॅरे.
  9. त्याचप्रमाणे जवळच्या लहान घटकाला उजवीकडील संचयित करण्यासाठी आकार n च्या आकाराचा एक अ‍ॅरे [] तयार करा. मूळ अ‍ॅरे a [] च्या उलट करा आणि दिलेल्या अ‍ॅरेसह लहान घटकांसाठी फंक्शनला कॉल करा, त्याचे आकार आहे आणि पॅरामीटर असल्यामुळे उजवे अ‍ॅरे.
  10. 0 ते एन -1 पर्यंत जा आणि डावे आणि उजवे अ‍ॅरेचा अधिकतम भिन्नता शोधा.
  11. निकाल प्रिंट करा.

कोड

नजीकच्या डाव्या आणि उजव्या छोट्या घटकांमध्ये जास्तीत जास्त फरक शोधण्यासाठी सी ++ प्रोग्राम

#include<bits/stdc++.h> 
using namespace std; 
  
void SmallerElement(int a[], int n, int SE[]){ 
    stack<int>S; 
  
    for(int i=0; i<n; i++){ 
        
        while(!S.empty() && S.top() >= a[i]){ 
            S.pop(); 
        }
  
        if(!S.empty()){ 
            SE[i] = S.top();
        }
  
        else{
            SE[i] = 0;
        }
  
        S.push(a[i]); 
    } 
} 
  
int findMaxDiff(int a[], int n){ 
    int left[n]; 
  
    SmallerElement(a, n, left); 
  
    int right[n]; 
    
    reverse(a, a + n); 
    SmallerElement(a, n, right); 
  
    int result = -1; 
    for(int i=0 ; i< n ; i++){ 
        result = max(result, abs(left[i] - right[n-1-i]));
    }
   
    return result; 
} 
  
int main(){ 
    int a[] = {2, 4, 8, 7, 7, 9, 3}; 
    int n = sizeof(a)/sizeof(a[0]);
    
    cout << findMaxDiff(a, n) << endl; 
    
    return 0; 
}
4

जवळच्या डाव्या आणि उजव्या छोट्या घटकांमध्ये जास्तीत जास्त फरक शोधण्यासाठी जावा प्रोग्राम

import java.util.*; 
  
class MaximumOfDifference{ 
  
    static void SmallerElement(int a[], int n, int SE[]){ 
        
        Stack<Integer> S = new Stack<>(); 
  
        for(int i = 0; i < n; i++){ 
            
            while(!S.empty() && S.peek() >= a[i]){ 
                S.pop(); 
            } 
  
            if(!S.empty()){ 
                SE[i] = S.peek(); 
            }  
            
            else{ 
                SE[i] = 0; 
            } 
  
            S.push(a[i]); 
        } 
    } 
  
    static int findMaxDiff(int a[], int n){ 
        int[] left = new int[n]; 
  
        SmallerElement(a, n, left); 
  
        int[] right = new int[n]; 
        
        reverse(a); 
        SmallerElement(a, n, right); 
  
        int result = -1; 
        for(int i = 0; i < n; i++){ 
            result = Math.max(result, Math.abs(left[i] - right[n - 1 - i])); 
        } 
 
        return result; 
    } 
  
    static void reverse(int a[]){ 
        int i, k, n = a.length, t; 
        
        for(i = 0; i < n / 2; i++){ 
            t = a[i]; 
            a[i] = a[n - i - 1]; 
            a[n - i - 1] = t; 
        } 
    } 
      
    public static void main(String args[]){ 
        int a[] = {2, 4, 8, 7, 7, 9, 3}; 
        int n = a.length; 
        
        System.out.println(findMaxDiff(a, n)); 
    } 
}
4

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

O (n) जेथे n दिलेल्या अ‍ॅरे a मधील पूर्णांक संख्या [] आहे. कारण आपण नुकताच अ‍ॅरेचा आढावा घेतला आहे त्यामुळे वेळची जटिलता रेखीय असते.

स्पेस कॉम्प्लेक्सिटी

ओ (एन) कारण आम्ही n घटकांसाठी जागा वापरली. आम्ही डावे आणि उजवे असे दोन अ‍ॅरे तयार केले आहेत. अशा प्रकारे अवकाशातील अवघडपणा देखील रेषात्मक आहे.