查找最接近的左側和右側較小元素之間的最大差異


難度級別 容易獎學金
經常問 風箏
排列

問題陳述

給定一個 排列 大小為n的a []。 問題“在最左邊和最右邊的較小元素之間找到最大差異”要求我們創建一個函數。 這樣,它將創建兩個數組left []和right [],分別代表最左邊的較小元素和右邊的較小元素。 然後找到左[i]-右[i]的數組絕對差的最大值。

查找最接近的左側和右側較小元素之間的最大差異

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

查找最左和最右較小元素之間最大差異的算法

  1. 初始化 排列 大小為n的a []。
  2. 創建一個函數以查找左側和右側數組的較小元素,這些較小的元素接受一個數組,它的大小以及一個用於存儲較小元素作為參數的數組。
  3. 創建一個 整數類型的數據結構。
  4. 遍歷數組a []。 當堆棧不為空並且堆棧頂部的元素大於或等於當前索引處數組a []中的元素時,請在堆棧的tp處彈出該元素。
  5. 檢查堆棧是否不為空,將較小元素的數組的當前索引值更新為堆棧頂部的元素。 否則,將較小元素的數組中當前索引處的值更新為0。
  6. 將值壓入/插入堆棧中數組a []中的當前索引處。
  7. 同樣,創建另一個函數以找到可以接受數組且其大小作為參數的最大差值。
  8. 創建一個大小為n的left []數組,以將最近的較小元素存儲到左側。 使用給定數組,其大小和左數組作為參數,調用較小元素的函數。
  9. 同樣,創建一個大小為n的數組right [],以在右邊存儲最近的較小元素。 反轉原始數組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

複雜度分析

時間複雜度

O(N) 其中n是給定數組a []中整數的數量。 因為我們剛剛遍歷了數組,所以時間複雜度是線性的。

空間複雜度

O(n),因為我們將空間用於n個元素。 我們創建了左右兩個數組。 因此,空間複雜度也是線性的。