Фарқи максималии байни унсурҳои хурдтарини чап ва ростро пайдо кунед


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Фуркайтҳо
тартиботи ҳарбӣ тӯда

Изҳороти мушкилот

Дода шудааст асал а [] андозаи n. Масъалаи "Фарқияти максималии байни унсурҳои хурдтарини чап ва ростро ёбед" аз мо хоҳиш мекунад, ки функсия эҷод кунем. Ҳамин тавр, он ду массивро ба чап [] ва рост [] месозад, ки мутаносибан унсури хурдтарини чап ва мутаносибан унсури хурдтари ростро нишон медиҳанд. Пас ҳадди фарқи мутлақи массивҳоро ба чап [i] - right [i] ёбед.

Фарқи максималии байни унсурҳои хурдтарини чап ва ростро пайдо кунед

мисол

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

Алгоритми ёфтани фарқи максималӣ байни унсурҳои хурдтарини чап ва рост

  1. Оғози an асал а [] андозаи n.
  2. Барои ёфтани унсурҳои хурд барои массиви чап ва рост, ки массивро қабул мекунанд, андозаи он ва массивро барои нигоҳ доштани унсурҳои хурдтар ҳамчун параметр иҷро кунед.
  3. Сохтани а яхдон сохтори маълумоти навъи бутун.
  4. Аз массиви a [] гузаред. Дар ҳоле, ки стек холӣ нест ва унсури болои стек аз унсури массиви a] дар индекси ҷорӣ калонтар ё ба он баробар аст, унсурро дар tp стек ҷойгир кунед.
  5. Санҷед, ки анбора холӣ нест, арзиши индекси ҷории массивро барои унсурҳои хурд ҳамчун унсури болои стек навсозӣ кунед. Дигарӣ арзиши индекси ҷории массивро барои унсурҳои хурд ҳамчун 0 навсозӣ мекунад.
  6. Арзиши индекси ҳозираро дар массиви [] дар стек гузоред / дохил кунед.
  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

Таҳлили мураккабӣ

Мураккабии вақт

Эй (н) ки дар он n адади бутунҳо дар массиви додашудаи a [] аст. Азбаски мо навакак массивро тай кардем, мураккабии вақт хатӣ аст.

Мураккабии фазо

O (n), зеро мо барои n унсур фазо истифода кардем. Мо ду массивро аз чап ва рост сохтаем. Ҳамин тариқ, мураккабии фазо низ хаттӣ аст.