Solda və Sağda Sonrakı Böyük İndekslərin Maksimum Məhsulu

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Məlumat dəsti Fourkites InfoEdge
Geyim QalaqBaxılıb 69

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Verilmiş bir array n ölçülü bir []. Vəziyyətdəki hər bir element üçün mən L [i] və R [i] tapıram, burada - L [i] = L-ə ən yaxın göstərici olduğu L [ən yaxın göstərici]> L [i] və ən yaxın göstərici <i. R [i] = i-yə ən yaxın göstərici, burada R [ən yaxın göstərici]> R [i] və ən yaxın göstərici> i. L [i] və ya R [i] üçün belə bir indeks yoxdursa, onu 0-da yeniləyin. L və R-nin məhsulunun maksimumunu tapın - LR Məhsulu [i] = L [i] * R [i].

Solda və Sağda Sonrakı Böyük İndekslərin Maksimum MəhsuluPin

misal

Giriş: a [] = {5, 4, 3, 4, 5}

Çıxış: 8

Giriş: a [] = {1, 1, 1, 1, 0, 1, 1, 1, 1, 1}

Çıxış: 24

Alqoritm

  1. N ölçülü bir [] massivi başladın.
  2. Ən yaxın elementin sol və sağ indeksini saxlamaq üçün iki başqa massivi işə salın.
  3. Bir yaradın qalaq. N-1-dən 0-a keçin və yığın boş deyilsə və [cari indeks] [stack.top () - 1]) -dən böyükdürsə, stack.top () - 1 indeksindəki sol dizini cari indeks olaraq yeniləyin. + 1. Üstü açın.
  4. Hazırkı indeks + 1-i yığına daxil edin.
  5. Sağ sıra üçün bir yığın yaradın. 0-dan n-1-ə keçin və yığın boş deyilsə və [cari indeks] [stack.top () - 1]) -dən böyük olarsa, indiki stack.top () - 1 indeksindəki sağ cərgəni yeniləyin. +1. Üstü açın.
  6. Hazırkı indeks + 1-i yığına daxil edin.
  7. Cavabları saxlamaq üçün dəyişən yaradın və onu -1 olaraq başladın. 0-dan n-1-ə keçin və cavab dəyişənini maksimum cavab dəyişəni və sol dizidəki və sağ cərgədəki indeksdəki dəyərlərin məhsulu kimi yeniləyin.
  8. Cavab dəyişənini qaytarın.

C ++ proqramı, soldan və sağdan yuxarıdakı indekslərin maksimum məhsulunu tapmaq üçün

#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 proqramı, soldan və sağdan yuxarıdakı indekslərin maksimum məhsulunu tapmaq üçün

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

Solda və sağda daha böyük indekslərin məhsulunu tapmaq üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi: O (n * n), burada n - a [] massivindəki elementlərin sayı.

Köməkçi məkan: O (n), çünki n əlavə yer istifadə etdik.

References

Crack Sistemi Dizayn Müsahibələri
Translate »