Знайсці максімальную розніцу паміж бліжэйшымі левым і правым меншымі элементамі


Узровень складанасці Лёгка
Часта пытаюцца ў Фуркайты
масіў Стэк

Пастаноўка праблемы

Улічваючы масіў 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 элементаў. Мы стварылі два масівы злева і справа. Такім чынам, касмічная складанасць таксама лінейная.