નજીકના ડાબી અને જમણી નાના તત્વો વચ્ચે મહત્તમ તફાવત શોધો


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે ફોરકાઇટ્સ
અરે સ્ટેક

સમસ્યા નિવેદન

આપેલ એક એરે a [] કદ n. સમસ્યા "નજીકના ડાબા અને જમણા નાના તત્વો વચ્ચે મહત્તમ તફાવત શોધો" અમને ફંકશન બનાવવા માટે કહે છે. જેમ કે તે બે એરે બનાવે છે [] અને જમણે [] ડાબી બાજુના નજીકના નાના તત્વને અને અનુક્રમે જમણી બાજુના નાના તત્વને રજૂ કરે છે. પછી એરે બાકીના મહત્તમ તફાવતને શોધી કા findો [i] - જમણું [i].

નજીકના ડાબી અને જમણી નાના તત્વો વચ્ચે મહત્તમ તફાવત શોધો

ઉદાહરણ

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

નજીકના ડાબા અને જમણા નાના તત્વો વચ્ચે મહત્તમ તફાવત શોધવા માટે અલ્ગોરિધમનો

  1. પ્રારંભ એક એરે a [] કદ n.
  2. ડાબી અને જમણી એરે માટે નાના તત્વો શોધવા માટે ફંક્શન બનાવો, જે એરે સ્વીકારે છે, તેનું કદ છે, અને નાના પરિમાણોને તેના પરિમાણો તરીકે સંગ્રહિત કરવા માટે એરે.
  3. બનાવો સ્ટેક પૂર્ણાંક પ્રકારનું ડેટા સ્ટ્રક્ચર.
  4. એરેથી પસાર થવું એક []. જ્યારે સ્ટેક ખાલી નથી અને સ્ટેકની ટોચ પરનું તત્વ વર્તમાન અનુક્રમણિકામાં એરે એ [] માંના તત્વ કરતા વધારે અથવા બરાબર છે, તે ઘટકને સ્ટેકની ટોચ પર પ popપ કરો.
  5. સ્ટેક ખાલી નથી કે નહીં તે તપાસો, નાના તત્વો માટે સ્ટેકની ટોચ પર તત્વ તરીકે એરેમાં વર્તમાન અનુક્રમણિકા પર મૂલ્ય અપડેટ કરો. બાકીના નાના તત્વો માટે એરેમાં વર્તમાન અનુક્રમણિકા પરના મૂલ્યને 0 તરીકે અપડેટ કરો.
  6. સ્ટેકમાં એક એરે [] માં વર્તમાન અનુક્રમણિકા પર મૂલ્ય દબાણ / દાખલ કરો.
  7. એ જ રીતે, મહત્તમ તફાવત શોધવા માટે બીજું ફંક્શન બનાવો જે એરે સ્વીકારે છે અને તેનું પરિમાણ હોવાથી તેનું કદ છે.
  8. ડાબી બાજુના નજીકના નાના તત્વને સંગ્રહિત કરવા માટે કદ n ની એરે ડાબી [] બનાવો. આપેલ એરે સાથેના નાના તત્વો માટે ફંક્શનને ક Callલ કરો, તે કદ છે, અને ડાબું એરે, જેમ કે તે પરિમાણ છે.
  9. એ જ રીતે, નજીકના નાના તત્વને જમણી બાજુએ સંગ્રહવા માટે કદ n ની એરે [[] ની એરે બનાવો. મૂળ એરે a [] ને ઉલટાવી અને આપેલ એરે સાથેના નાના તત્વો માટે ફંક્શનને ક callલ કરો, તેનું કદ, અને પરિમાણ હોવાને કારણે જમણી એરે.
  10. 0 થી n-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

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન) જ્યાં n આપેલ એરેમાં પૂર્ણાંકોની સંખ્યા છે []. કારણ કે આપણે હમણાં જ એરે ઓળંગી ગયા છે તેથી સમય જટિલતા રેખીય છે.

અવકાશ જટિલતા

ઓ (એન) કારણ કે અમે n તત્વો માટે જગ્યાનો ઉપયોગ કર્યો છે. આપણે ડાબે અને જમણે બે એરે બનાવી છે. આમ જગ્યા જટિલતા પણ રેખીય છે.