निकटतम बाएँ और दाएँ छोटे तत्वों के बीच अधिकतम अंतर खोजें


कठिनाई स्तर आसान
में अक्सर पूछा चौपाई
ऐरे धुआँरा

समस्या का विवरण

दिया गया सरणी [a] आकार n। समस्या "निकटतम बाएं और दाएं छोटे तत्वों के बीच अधिकतम अंतर ढूंढें" हमें एक फ़ंक्शन बनाने के लिए कहता है। ऐसा है कि यह दो सरणियों को छोड़ देता है [] और दाएं [] क्रमशः बाएं और निकटतम छोटे तत्व के निकटतम छोटे तत्व का प्रतिनिधित्व करता है। फिर बायें [i] - दाएं [i] के पूर्ण अंतर का अधिकतम पता लगाएं।

निकटतम बाएँ और दाएँ छोटे तत्वों के बीच अधिकतम अंतर खोजें

उदाहरण

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

एल्गोरिथ्म निकटतम बाएँ और दाएँ छोटे तत्वों के बीच अधिकतम अंतर खोजने के लिए

  1. इनिशियलाइज़ a सरणी [a] आकार n।
  2. सरणी के लिए छोटे तत्वों को खोजने के लिए एक फ़ंक्शन बनाएं बाएं और दाएं जो एक सरणी को स्वीकार करते हैं, यह आकार है, और छोटे तत्वों को संग्रहीत करने के लिए एक सरणी है क्योंकि यह पैरामीटर है।
  3. बनाओ धुआँरा पूर्णांक प्रकार की डेटा संरचना।
  4. सरणी के माध्यम से पार करना []। जबकि स्टैक खाली नहीं है और स्टैक के शीर्ष पर मौजूद तत्व एरे [a] में तत्व से अधिक या बराबर है, स्टैक के tp पर तत्व को पॉप करें।
  5. जांचें कि क्या स्टैक खाली नहीं है, स्टैक के शीर्ष पर तत्व के रूप में छोटे तत्वों के लिए सरणी में वर्तमान सूचकांक पर मूल्य को अपडेट करें। एल्स 0 के रूप में छोटे तत्वों के लिए सरणी में वर्तमान सूचकांक में मूल्य को अपडेट करता है।
  6. स्टैक में सरणी [] में वर्तमान सूचकांक में मूल्य को पुश / सम्मिलित करें।
  7. इसी प्रकार, एक अंतर को खोजने के लिए एक और फ़ंक्शन बनाएं जो किसी सरणी को स्वीकार करता है और इसका आकार पैरामीटर है।
  8. बाईं ओर के निकटतम छोटे तत्व को संग्रहीत करने के लिए आकार n के बाईं ओर एक सरणी बनाएं। दिए गए एरे के साथ छोटे तत्वों के लिए फ़ंक्शन को कॉल करें, यह आकार है, और बाएं सरणी के रूप में यह पैरामीटर है।
  9. इसी प्रकार, दाईं ओर के निकटतम छोटे तत्व को संग्रहीत करने के लिए n के आकार की एक सरणी सही [] बनाएं। मूल सरणी को उल्टा करें [] और दिए गए सरणी के साथ छोटे तत्वों के लिए फ़ंक्शन को कॉल करें, यह आकार है, और सही सरणी यह ​​पैरामीटर है।
  10. 0 से n-1 तक ट्रैवस करें और बाएं और दाएं सरणी के पूर्ण अंतर का अधिकतम पता लगाएं।
  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 तत्वों के लिए स्थान का उपयोग किया है। हमने बाएँ और दाएँ दो सरणियाँ बनाई हैं। इस प्रकार अंतरिक्ष की जटिलता भी रैखिक है।