അടുത്തുള്ള ഇടത്, വലത് ചെറിയ ഘടകങ്ങൾ തമ്മിലുള്ള പരമാവധി വ്യത്യാസം കണ്ടെത്തുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ഫോർകൈറ്റുകൾ
അറേ കൂനകൂട്ടുക

പ്രശ്നം പ്രസ്താവന

ഒരു നൽകി ശ്രേണി a [] വലുപ്പം n. “അടുത്തുള്ള ഇടത്, വലത് ചെറിയ ഘടകങ്ങൾ തമ്മിലുള്ള പരമാവധി വ്യത്യാസം കണ്ടെത്തുക” എന്ന പ്രശ്നം ഒരു ഫംഗ്ഷൻ സൃഷ്ടിക്കാൻ ഞങ്ങളോട് ആവശ്യപ്പെടുന്നു. ഇടത് വശത്ത് ഏറ്റവും അടുത്തുള്ള ചെറിയ ഘടകത്തെയും വലതുവശത്ത് ഏറ്റവും അടുത്തുള്ള ചെറിയ ഘടകത്തെയും പ്രതിനിധീകരിക്കുന്ന രണ്ട് അറേകൾ ഇടത് [], വലത് [] എന്നിവ സൃഷ്ടിക്കുന്നു. ഇടത് [i] - വലത് [i] അറേകളുടെ കേവല വ്യത്യാസത്തിന്റെ പരമാവധി കണ്ടെത്തുക.

അടുത്തുള്ള ഇടത്, വലത് ചെറിയ ഘടകങ്ങൾ തമ്മിലുള്ള പരമാവധി വ്യത്യാസം കണ്ടെത്തുക

ഉദാഹരണം

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

ഏറ്റവും അടുത്തുള്ള ഇടത്, വലത് ചെറിയ ഘടകങ്ങൾ തമ്മിലുള്ള പരമാവധി വ്യത്യാസം കണ്ടെത്താനുള്ള അൽഗോരിതം

  1. ഒരു സമാരംഭിക്കുക ശ്രേണി a [] വലുപ്പം n.
  2. ഒരു അറേ, അതിന്റെ വലുപ്പം, ചെറിയ ഘടകങ്ങൾ അതിന്റെ പാരാമീറ്ററുകൾ പോലെ സംഭരിക്കുന്നതിനുള്ള ഒരു അറേ എന്നിവ സ്വീകരിക്കുന്ന ഇടത്, വലത് അറേയ്‌ക്കായി ചെറിയ ഘടകങ്ങൾ കണ്ടെത്തുന്നതിന് ഒരു ഫംഗ്ഷൻ സൃഷ്‌ടിക്കുക.
  3. സൃഷ്ടിക്കുക സ്റ്റാക്ക് പൂർണ്ണസംഖ്യയുടെ ഡാറ്റാ ഘടന.
  4. അറേയിലൂടെ സഞ്ചരിക്കുക a []. സ്റ്റാക്ക് ശൂന്യമല്ലെങ്കിലും സ്റ്റാക്കിന്റെ മുകളിലുള്ള ഘടകം നിലവിലെ സൂചികയിലെ അറേ [[] ലെ ഘടകത്തെക്കാൾ വലുതോ തുല്യമോ ആണെങ്കിൽ, സ്റ്റാക്കിന്റെ ടിപിയിൽ ഘടകം പോപ്പ് ചെയ്യുക.
  5. സ്റ്റാക്ക് ശൂന്യമല്ലെങ്കിൽ പരിശോധിക്കുക, സ്റ്റാക്കിന്റെ മുകളിലുള്ള ഘടകമായി ചെറിയ ഘടകങ്ങൾക്കായി അറേയിലെ നിലവിലെ സൂചികയിലെ മൂല്യം അപ്‌ഡേറ്റുചെയ്യുക. ചെറിയ ഘടകങ്ങൾ‌ക്കായി അറേയിലെ നിലവിലെ സൂചികയിലെ മൂല്യം 0 ആയി അപ്‌ഡേറ്റുചെയ്യുക.
  6. നിലവിലെ സൂചികയിൽ മൂല്യം ഒരു [] അറേയിലെ പുഷ് / തിരുകുക.
  7. അതുപോലെ, ഒരു ശ്രേണി സ്വീകരിക്കുന്ന പരമാവധി വ്യത്യാസം കണ്ടെത്തുന്നതിന് മറ്റൊരു ഫംഗ്ഷൻ സൃഷ്ടിക്കുക, അതിന്റെ വലുപ്പം അതിന്റെ പാരാമീറ്ററാണ്.
  8. ഇടത് വശത്ത് ഏറ്റവും അടുത്തുള്ള ചെറിയ ഘടകം സംഭരിക്കുന്നതിന് വലിപ്പം n ന്റെ ഒരു അറേ സൃഷ്ടിക്കുക. തന്നിരിക്കുന്ന അറേയുള്ള ചെറിയ ഘടകങ്ങൾക്കായുള്ള ഫംഗ്ഷനെ വിളിക്കുക, അതിന്റെ വലുപ്പം, ഇടത് അറേ അതിന്റെ പാരാമീറ്റർ.
  9. അതുപോലെ, ഏറ്റവും അടുത്തുള്ള ചെറിയ ഘടകം വലതുവശത്ത് സംഭരിക്കുന്നതിന് വലിപ്പം n ന്റെ ഒരു അറേ വലത് സൃഷ്ടിക്കുക. ഒറിജിനൽ അറേയെ ഒരു [] വിപരീതമാക്കുകയും തന്നിരിക്കുന്ന അറേ ഉപയോഗിച്ച് ചെറിയ ഘടകങ്ങൾക്കായി ഫംഗ്ഷൻ വിളിക്കുകയും ചെയ്യുക, അതിന്റെ വലുപ്പം, വലത് അറേ അതിന്റെ പാരാമീറ്റർ.
  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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (n) ഇവിടെ n എന്നത് തന്നിരിക്കുന്ന അറേയിലെ പൂർണ്ണസംഖ്യകളുടെ എണ്ണം a []. കാരണം നമ്മൾ ഇപ്പോൾ അറേയിലൂടെ സഞ്ചരിച്ചതിനാൽ സമയ സങ്കീർണ്ണത രേഖീയമാണ്.

ബഹിരാകാശ സങ്കീർണ്ണത

O (n) കാരണം ഞങ്ങൾ n ഘടകങ്ങൾക്ക് ഇടം ഉപയോഗിച്ചു. ഇടതും വലതും രണ്ട് അറേകൾ ഞങ്ങൾ സൃഷ്ടിച്ചു. അങ്ങനെ സ്ഥല സങ്കീർണ്ണതയും രേഖീയമാണ്.