नजिकको बाँया र दाँया साना तत्वहरू बीच अधिकतम फरक फेला पार्नुहोस्


कठिनाई तह सजिलो
बारम्बार सोधिन्छ फोरकाइट्स
एरे थाक

समस्या वक्तव्य

दिइएको array a [] आकार n को। समस्या "नजीकको बाँया र दायाँ साना तत्वहरू बीच अधिकतम भिन्नता फेला पार्नुहोस्" हामीलाई प्रकार्य सिर्जना गर्न सोध्छ। यस्तो कि यसले दुई एर्रेहरू बायाँ [] र दायाँ [] बायाँको नजिकको सानो तत्व प्रतिनिधित्व गर्दछ र क्रमशः दाँयामा करीव सानो तत्त्व प्रतिनिधित्व गर्दछ। त्यसो भए बाँकी एर्रेको पूर्ण भिन्नताको अधिकतम फेला पार्नुहोस् [i] - दाँया [i]।

नजिकको बाँया र दाँया साना तत्वहरू बीच अधिकतम फरक फेला पार्नुहोस्

उदाहरणका

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

नजिकको बायाँ र दायाँ साना तत्वहरूमा अधिकतम भिन्नता पत्ता लगाउन एल्गोरिथ्म

  1. सुरु गर्नुहोस् array a [] आकार n को।
  2. एर्रेको दायाँ र दायाँका लागि सानो तत्वहरू फेला पार्न एउटा प्रकार्य सिर्जना गर्नुहोस् जुन एर्रे स्वीकार्छ, यसको साइज हो, र एरामेराको रूपमा सानो तत्वहरू भण्डार गर्न एर्रे हुन्छ किनकि यो प्यारामिटर हुन्छ।
  3. एक सिर्जना गर्नुहोस् स्ट्याक पूर्णांक प्रकारको डेटा संरचना।
  4. एर्रे ए [] बाट पार गर्नुहोस्। जबकि स्ट्याक खाली छैन र स्ट्याकको शीर्षमा एलिमेन्ट वर्तमानको सूचकांकमा एरे [a] मा भएको एलिमेन्ट भन्दा ठूलो वा बराबर छ, तत्वलाई स्ट्याकको tp मा पप गर्नुहोस्।
  5. यदि स्ट्याक खाली छैन भने जाँच गर्नुहोस्, सानामा वर्तमान सूचकांकमा मान अपडेट गर्नुहोस् सानो तत्वहरूको लागि स्ट्याकको माथि एलिमेन्टको रूपमा। नत्र ० मा सानो तत्वका लागि एरेमा वर्तमान सूचकांकमा मान अपडेट गर्नुहोस्।
  6. स्ट्याकमा एरे [[] एरेमा हालको इन्डेक्समा मान थिच्नुहोस् / घुसाउनुहोस्।
  7. त्यस्तै भिन्नताको अधिकतम फेला पार्न अर्को प्रकार्य सिर्जना गर्नुहोस् जुन एर्रे स्वीकार्छ र यो प्यारामिटरको रूपमा यसको साइज हो।
  8. बाँयाको नजिकको सानो तत्व भण्डारण गर्न आकार एनको बायाँ [] एन्रे सिर्जना गर्नुहोस्। दिइएको एर्रेको साथ सानो तत्वहरूको लागि प्रकार्य कल गर्नुहोस्, यो साइज हो, र बायाँ एर्रे यो प्यारामिटरको रूपमा।
  9. त्यस्तै गरी, दायराको नजिकको सानो तत्व भण्डार गर्न आकार एनको एक एर्रे [] आकार सिर्जना गर्नुहोस्। मूल एर्रे a [] उल्टाउनुहोस् र दिईएको एर्रेको साथ सानो एलिमेन्टहरूका लागि प्रकार्य कल गर्नुहोस्, यसको साइज, र सहि एर्रे यो प्यारामिटरको रूपमा।
  10. ० देखि n-१ सम्म ट्र्याभर्स गर्नुहोस् र बाँया र दाँया एर्रेको अधिकतम पूर्ण भिन्नता फेला पार्नुहोस्।
  11. परिणाम प्रिन्ट गर्नुहोस्।

कोड

C ++ कार्यक्रम नजिकको बाँया र दायाँ सानो तत्वहरू बीच अधिकतम भिन्नता फेला पार्न

#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

जटिलता विश्लेषण

समय जटिलता

ऊ) जहाँ n दिइएको एरेमा पूर्णांकको संख्या हो []। किनकि हामीले भर्खर एरे पार गरिसकेका छौं यसैले समय जटिलता रैखिक छ।

ठाउँ जटिलता

O (n) किनभने हामीले n तत्वहरूको लागि ठाउँ प्रयोग गर्‍यौं। हामीले बाँया र दायाँ दुई एर्रेहरू सिर्जना गरेका छौं। यसैले स्पेस जटिलता पनि रैखिक छ।