תוצר מקסימלי של אינדקסים של הבא הבא על שמאל וימין


רמת קושי בינוני
נשאל לעתים קרובות סט עובדות פורקיטים InfoEdge
מערך לערום

ניתנת מערך א [] בגודל n. עבור כל אלמנט במיקום, אני מוצא את L [i] ו- R [i] איפה - L [i] = האינדקס הקרוב ביותר ל- i כאשר L [האינדקס הקרוב ביותר]> L [i] והמדד הקרוב ביותר <i. R [i] = האינדקס הקרוב ביותר ל- i כאשר R [האינדקס הקרוב ביותר]> R [i] והמדד הקרוב ביותר> i. אם לא קיים אינדקס כזה עבור L [i] או R [i] עדכן אותו ב- 0. מצא את המקסימום של המוצר של L ו- R כאשר - LR Product [i] = L [i] * R [i].

תוצר מקסימלי של אינדקסים של הבא הבא על שמאל וימין

דוגמה

קלט: a [] = {5, 4, 3, 4, 5}

פלט: 8

קלט: a [] = {1, 1, 1, 1, 0, 1, 1, 1, 1, 1}

פלט: 24

אַלגוֹרִיתְם

  1. אתחל מערך a [] בגודל n.
  2. אתחל שני מערכים אחרים לאחסון האינדקס השמאלי והימני של האלמנט הגדול יותר.
  3. צור לערום. חצה מ n-1 ל 0 ובעוד המחסנית אינה ריקה ואינדקס הנוכחי גדול מ- [stack.top () - 1]), עדכן את המערך השמאלי ב- index stack.top () - 1 כאינדקס הנוכחי + 1. פופ למעלה.
  4. הכנס את האינדקס הנוכחי + 1 לערימה.
  5. עבור מערך נכון ליצור ערימה. מעבר בין 0 ל n-1 ובעוד המחסנית אינה ריקה [אינדקס הנוכחי] גדול מ- [stack.top () - 1]), עדכן את המערך הנכון באינדקס stack.top () - 1 כאינדקס הנוכחי +1. פופ למעלה.
  6. הכנס את האינדקס הנוכחי + 1 לערימה.
  7. צור משתנה לאחסון תשובות ואותחל אותו כ -1. חצה בין 0 ל- n-1 ועדכן את משתנה התשובה כמקסימום משתנה התשובה ותוצר של ערכים באינדקס הנוכחי במערך השמאלי ובמערך הימני.
  8. החזירו את משתנה התשובה.

תוכנית C ++ למציאת המוצר המרבי של האינדקסים של הגדולים הבאים בימין ומשמאל

#include <bits/stdc++.h> 
using namespace std; 
#define MAX 1000 
  
vector<int> nextGreaterInLeft(int a[], int n){ 
    vector<int> left_index(MAX, 0); 
    stack<int> s; 
  
    for(int i = n - 1; i >= 0; i--){ 
  
        while(!s.empty() && a[i] > a[s.top() - 1]){ 
            int r = s.top(); 
            s.pop(); 
  
            left_index[r - 1] = i + 1; 
        } 
  
        s.push(i + 1); 
    } 
    return left_index; 
} 
  
vector<int> nextGreaterInRight(int a[], int n){ 
    vector<int> right_index(MAX, 0); 
    stack<int> s; 
    
    for(int i = 0; i < n; ++i){ 
  
        while(!s.empty() && a[i] > a[s.top() - 1]){ 
            int r = s.top(); 
            s.pop(); 
  
            right_index[r - 1] = i + 1; 
        } 
  
        s.push(i + 1); 
    } 
    return right_index; 
} 
  
int Product(int a[], int n){ 
    
    vector<int> left = nextGreaterInLeft(a, n); 
  
    vector<int> right = nextGreaterInRight(a, n); 
    int ans = -1; 
    
    for(int i = 1; i <= n; i++){ 
        ans = max(ans, left[i] * right[i]); 
    } 
  
    return ans; 
} 
  
int main(){ 
    int a[] = {5, 4, 3, 4, 5}; 
    int n = sizeof(a)/sizeof(a[1]); 
  
    cout<<Product(a, n); 
  
    return 0; 
}
8

תוכנית Java כדי למצוא את התוצר המרבי של האינדקסים של הגדולים הבאים בימין ומשמאל

import java.io.*; 
import java.util.*; 
  
class LRProduct{ 
    static int MAX = 1000; 
      
    static int[] nextGreaterInLeft(int []a, int n){ 
        int []left_index = new int[MAX]; 
        Stack<Integer> s = new Stack<Integer>(); 
      
        for(int i = n-1; i >= 0; i--){ 
      
            while (s.size() != 0 && a[i] > a[s.peek() - 1]){ 
                int r = s.peek(); 
                s.pop(); 
      
                left_index[r - 1] = i + 1; 
            } 
      
            s.push(i + 1); 
        } 
        return left_index; 
    } 
      
    static int[] nextGreaterInRight(int []a, int n){
        
        int []right_index = new int[MAX]; 
        Stack<Integer> s = new Stack<Integer>(); 
        
        for(int i = 0; i < n; ++i){ 
      
            while (s.size() != 0 && a[i] > a[s.peek() - 1]){ 
                int r = s.peek(); 
                s.pop(); 
      
                right_index[r - 1] = i + 1; 
            } 
      
            s.push(i + 1); 
        } 
        return right_index; 
    } 
      
    static int Product(int []a, int n){ 
          
        int []left = nextGreaterInLeft(a, n); 
      
        int []right = nextGreaterInRight(a, n); 
        int ans = -1; 
        
        for(int i = 1; i <= n; i++){ 
            ans = Math.max(ans, left[i] * right[i]); 
        } 
      
        return ans; 
    } 
      
    public static void main(String args[]){
        
        int []a = new int[]{5, 4, 3, 4, 5}; 
        int n = a.length; 
      
        System.out.print(Product(a, n)); 
    } 
} 
8

ניתוח מורכבות למציאת התוצר המקסימלי של אינדקסים גדולים יותר בימין ומשמאל

מורכבות זמן: O (n * n) כאשר n הוא מספר האלמנטים במערך a [].

מרחב עזר: O (n) כי השתמשנו ב- n שטח נוסף.

הפניות