Хамгийн ойрын зүүн ба баруун жижиг элементүүдийн хоорондох хамгийн их ялгааг олох


Хэцүү байдлын түвшин Easy
Байнга асуудаг Фуркайт
Array Stack

Асуудлын мэдэгдэл

Өгсөн массив n хэмжээтэй [[. "Хамгийн ойрын зүүн ба баруун жижиг элементүүдийн хоорондох хамгийн их ялгааг олох" асуудал нь функцийг бий болгохыг биднээс хүсдэг. Ингэснээр зүүн [] ба баруун [] гэсэн хоёр массивыг зүүн тийш нь хамгийн бага, баруун талд нь хамгийн бага элементийг тус тус харуулна. Дараа нь зүүн [i] - баруун [i] массивын үнэмлэхүй зөрүүний дээд хэмжээг ол.

Хамгийн ойрын зүүн ба баруун жижиг элементүүдийн хоорондох хамгийн их ялгааг олох

Жишээ нь

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

Хамгийн ойрын зүүн ба баруун элементүүдийн хоорондох хамгийн их зөрүүг олох алгоритм

  1. Эхлүүлэх массив n хэмжээтэй [[.
  2. Массивыг хүлээн авах массивын хэмжээ зүүн, баруун талд байх жижиг элементүүдийг олох функцийг үүсгэж, жижиг элементүүдийг параметр болгон хадгалах массивыг байгуул.
  3. Бүтээх стек бүхэл тооны өгөгдлийн бүтэц.
  4. A [] массивыг дайран өнгөр. Стек хоосон биш бөгөөд стекийн дээд талын элемент нь одоогийн индекс дэх [] массивын элементээс их буюу тэнцүү байх үед элементийг стекийн tp хэсэгт байрлуулна.
  5. Стек хоосон биш байгаа эсэхийг шалгаж, массив дахь одоогийн индекс дэх утгыг стекийн дээд хэсэгт байрлах элемент болгон шинэчил. Бусад массив дахь одоогийн индекс дэх утгыг 0 гэж жижиг элементүүдэд шинэчлэх.
  6. Стек дэх a] массив дахь одоогийн индекс дээрх утгыг түлхэх / оруулах.
  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

Java програм нь хамгийн ойрын зүүн ба баруун жижиг элементүүдийн хоорондох хамгийн их ялгааг олох

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 нь өгөгдсөн а [] массив дахь бүхэл тоонуудын тоо юм. Бид дөнгөж массивыг туулсан тул цаг хугацааны нарийн төвөгтэй байдал нь шугаман байна.

Сансрын нарийн төвөгтэй байдал

O (n), учир нь бид n элементийн орон зайг ашигласан. Бид баруун, зүүн гэсэн хоёр массив үүсгэсэн. Тиймээс орон зайн нарийн төвөгтэй байдал нь мөн шугаман юм.