Знайдіть максимальну різницю між найближчим лівим та правим меншими елементами


Рівень складності Легко
Часто запитують у Фуркіти
масив Стек

Постановка проблеми

З огляду на масив 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 []. Поки стек не порожній, а елемент у верхній частині стека більший або дорівнює елементу в масиві a [] за поточним індексом, виведіть елемент на tp стека.
  5. Перевірте, чи стек не порожній, оновіть значення в поточному індексі в масиві для менших елементів як елемент у верхній частині стека. В іншому випадку оновіть значення поточного індексу в масиві для менших елементів як 0.
  6. Натисніть / вставте значення в поточному індексі в масив a [] у стеку.
  7. Подібним чином створіть іншу функцію, щоб знайти максимальну різницю, яка приймає масив і його розмір як його параметр.
  8. Створіть масив ліворуч [] розміром n, щоб зберегти найближчий менший елемент ліворуч. Викличте функцію для менших елементів із заданим масивом, його розміром та лівим масивом як його параметром.
  9. Подібним чином створіть масив право [] розміром n, щоб зберігати найближчий менший елемент праворуч. Змініть початковий масив a [] і викличте функцію для менших елементів із заданим масивом, його розміром і правильним масивом як параметром.
  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

Аналіз складності

Складність часу

О (п) де n - кількість цілих чисел у даному масиві a []. Оскільки ми щойно пройшли масив, таким чином складність часу є лінійною.

Складність простору

O (n), оскільки ми використовували простір для n елементів. Ми створили два масиви ліворуч і праворуч. Таким чином, складність простору також є лінійною.