왼쪽과 오른쪽에 다음 큰 인덱스의 최대 곱

난이도 중급
자주 묻는 질문 팩트 셋 포카이트 인포에지
배열 스택조회수 38

주어진 정렬 크기 n의 a []. 위치의 각 요소에 대해 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. n 크기의 배열 a []를 초기화합니다.
  2. 가장 가까운 큰 요소의 왼쪽 및 오른쪽 인덱스를 저장하기 위해 두 개의 다른 배열을 초기화합니다.
  3. 만들기 스택. n-1에서 0으로 트래버스하고 스택이 비어 있지 않고 a [current index]가 a [stack.top () – 1])보다 크면 인덱스 stack.top () – 1에서 현재 인덱스로 왼쪽 배열을 업데이트합니다. + 1. 상단을 팝니다.
  4. 스택에 현재 index + 1을 삽입합니다.
  5. 올바른 배열의 경우 스택을 만듭니다. 0에서 n-1로 이동하고 스택이 비어 있지 않고 a [현재 인덱스]가 a [stack.top () – 1])보다 크면 인덱스 stack.top () – 1에서 현재 인덱스로 오른쪽 배열을 업데이트합니다. +1. 상단을 팝니다.
  6. 스택에 현재 index + 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 개의 추가 공간을 사용했기 때문입니다.

참조

Translate »