ຊອກຫາຄວາມແຕກຕ່າງກັນສູງສຸດລະຫວ່າງອົງປະກອບນ້ອຍທີ່ຢູ່ເບື້ອງຊ້າຍແລະຂວາທີ່ໃກ້ທີ່ສຸດ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ ສີ່ພັນ
Array Stack

ຖະແຫຼງການບັນຫາ

ມອບໃຫ້ array a [] ຂອງຂະ ໜາດ n. ບັນຫາ "ຊອກຫາຄວາມແຕກຕ່າງສູງສຸດລະຫວ່າງອົງປະກອບນ້ອຍທີ່ຢູ່ເບື້ອງຊ້າຍແລະຂວາທີ່ໃກ້ທີ່ສຸດ" ຂໍໃຫ້ພວກເຮົາສ້າງ ໜ້າ ທີ່. ສິ່ງດັ່ງກ່າວມັນສ້າງສອງຂອດຊ້າຍ [] ແລະເບື້ອງຂວາ [] ເປັນຕົວແທນຂອງອົງປະກອບນ້ອຍທີ່ໃກ້ທີ່ສຸດໄປທາງຊ້າຍແລະໃກ້ຄຽງທີ່ນ້ອຍທີ່ສຸດຢູ່ທາງຂວາຕາມ ລຳ ດັບ. ຫຼັງຈາກນັ້ນ, ຊອກຫາຈຸດສູງສຸດຂອງຄວາມແຕກຕ່າງຢ່າງແທ້ຈິງຂອງບັນດາຂວດຊ້າຍ [i] - ຖືກຕ້ອງ [i].

ຊອກຫາຄວາມແຕກຕ່າງກັນສູງສຸດລະຫວ່າງອົງປະກອບນ້ອຍທີ່ຢູ່ເບື້ອງຊ້າຍແລະຂວາທີ່ໃກ້ທີ່ສຸດ

ຍົກຕົວຢ່າງ

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

ສູດການຄິດໄລ່ເພື່ອຊອກຫາຄວາມແຕກຕ່າງສູງສຸດລະຫວ່າງອົງປະກອບນ້ອຍທີ່ນ້ອຍທີ່ສຸດທີ່ຢູ່ເບື້ອງຊ້າຍແລະຂວາ

  1. ເລີ່ມຕົ້ນເປັນ array a [] ຂອງຂະ ໜາດ n.
  2. ສ້າງຟັງຊັນເພື່ອຊອກຫາອົງປະກອບນ້ອຍກວ່າ ສຳ ລັບຂີດຊ້າຍແລະຂວາທີ່ຍອມຮັບອາເລ, ມັນມີຂະ ໜາດ ແລະເປັນແຖວເພື່ອເກັບຮັກສາອົງປະກອບນ້ອຍໆໃຫ້ເປັນຕົວ ກຳ ນົດ.
  3. ສ້າງເປັນ stack ໂຄງສ້າງຂໍ້ມູນຂອງປະເພດເລກເຕັມ.
  4. ຂ້າມຜ່ານອາເລ a []. ໃນຂະນະທີ່ stack ບໍ່ຫວ່າງແລະອົງປະກອບທີ່ຢູ່ເທິງສຸດຂອງ stack ແມ່ນໃຫຍ່ກ່ວາຫຼືເທົ່າກັບອົງປະກອບທີ່ array ໃນ [] ທີ່ດັດຊະນີປັດຈຸບັນ, pop the element ທີ່ຢູ່ tp ຂອງ stack.
  5. ກວດເບິ່ງວ່າ stack ບໍ່ແມ່ນຫວ່າງ, ປັບປຸງມູນຄ່າທີ່ດັດສະນີປັດຈຸບັນເປັນອາເລ ສຳ ລັບອົງປະກອບນ້ອຍກວ່າເປັນອົງປະກອບທີ່ຢູ່ເທິງສຸດຂອງ stack. ປັບປຸງຄ່າອື່ນໃນດັດຊະນີປັດຈຸບັນໃນອາເລ ສຳ ລັບອົງປະກອບນ້ອຍກວ່າ 0.
  6. ຍູ້ / ໃສ່ຄ່າໃນດັດຊະນີປັດຈຸບັນໃນ array a [] ໃນ stack.
  7. ເຊັ່ນດຽວກັນ, ສ້າງ ໜ້າ ທີ່ອື່ນເພື່ອຊອກຫາຄວາມແຕກຕ່າງສູງສຸດທີ່ຍອມຮັບອາເລແລະມັນມີຂະ ໜາດ ເທົ່າກັບພາລາມິເຕີ.
  8. ສ້າງອາເລທີ່ຢູ່ເບື້ອງຊ້າຍ [] ຂອງຂະ ໜາດ n ເພື່ອເກັບສ່ວນປະກອບນ້ອຍກວ່າຢູ່ເບື້ອງຊ້າຍ. ໂທຫາຟັງຊັນ ສຳ ລັບອົງປະກອບທີ່ນ້ອຍກວ່າດ້ວຍອາເລທີ່ໃຫ້, ມັນມີຂະ ໜາດ, ແລະຂບວນເບື້ອງຊ້າຍຍ້ອນວ່າມັນເປັນພາລາມິເຕີ.
  9. ເຊັ່ນດຽວກັນ, ສ້າງ array ທີ່ຖືກຕ້ອງຂອງຂະ ໜາດ n ເພື່ອເກັບຮັກສາອົງປະກອບນ້ອຍທີ່ໃກ້ທີ່ສຸດໄວ້ທາງຂວາ. ປີ້ນກັບຂບວນຕົ້ນສະບັບ a [] ແລະເອີ້ນຟັງຊັນ ສຳ ລັບອົງປະກອບນ້ອຍກວ່າດ້ວຍອາເລທີ່ໃຫ້, ຂະ ໜາດ ຂອງມັນແລະແຖວທີ່ ເໝາະ ສົມຍ້ອນວ່າມັນເປັນພາລາມິເຕີ.
  10. Traverse ຈາກ 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 Program ເພື່ອຊອກຫາຄວາມແຕກຕ່າງສູງສຸດລະຫວ່າງອົງປະກອບນ້ອຍທີ່ນ້ອຍທີ່ສຸດທີ່ຢູ່ເບື້ອງຊ້າຍແລະຂວາ

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. ພວກເຮົາໄດ້ສ້າງສອງຕາຕະລາງຊ້າຍແລະຂວາ. ດັ່ງນັ້ນຄວາມສັບສົນໃນພື້ນທີ່ຍັງເປັນເສັ້ນ.