C++에서 가장 가까운 왼쪽과 오른쪽 작은 요소 간의 최대 차이 찾기

컨셉

주어진 정수 배열과 관련하여 우리의 임무는 배열에 있는 모든 요소의 가장 가까운 왼쪽과 오른쪽 작은 요소 사이의 최대 절대차를 결정하는 것입니다. 오른쪽 또는 왼쪽에 작은 요소가 없는 경우 어떤 요소의 측면에서 우리는 0을 더 작은 요소로 받아들입니다. 여기에서 예를 들어 가장 왼쪽에 있는 요소의 경우 왼쪽에 있는 가장 가까운 작은 요소를 0으로 설정합니다. 마찬가지로 가장 오른쪽에 있는 요소의 경우 오른쪽에 있는 작은 요소를 0으로 설정합니다.

입력

arr[] = {3, 2, 9}

출력

2

왼쪽 작은 LS[] {0, 0, 2}

오른쪽 작은 RS[] {2, 0, 0}

abs의 최대 차이(LS[i] - RS[i]) =2 - 0 =2

입력

arr[] = {3, 5, 9, 8, 8, 10, 4}

출력

4

왼쪽 작은 LS[] ={0, 3, 5, 5, 5, 8, 3}

오른쪽 작은 RS[] ={0, 4, 8, 4, 4, 4, 0}

abs의 최대 차이(LS[i] - RS[i]) =8 - 4 =4

방법

가장 가까운 왼쪽 및 오른쪽 작은 요소를 영원히 찾고 왼쪽과 오른쪽 작은 요소 간의 최대 차이를 업데이트한 후 O(n^2) 시간을 소비하는 간단한 솔루션을 적용합니다.

다시 O(n) 시간을 소비하는 효율적인 솔루션을 구현합니다. 여기서는 스택을 구현합니다. 여기서 흥미로운 부분은 동일한 함수를 사용하여 왼쪽과 오른쪽을 모두 작게 계산한다는 것입니다.

입력 배열이 'Array[]'이고 배열의 크기가 'n'이라고 가정합니다.

왼쪽의 모든 작은 요소 결정

• 새 빈 스택 S와 배열 LS[]를 만듭니다.
• 이제 입력 Array[]의 모든 요소 'Array[i]'에 대해, 여기서 'i'는 0에서 n-1로 이동합니다.
  • S가 비어 있지 않고 S의 맨 위 요소가 'Array[i]':pop S보다 크거나 같은 동안
  • S가 비어 있는 경우:'Array[i]'에는 이전에 더 작은 값이 없습니다.LS[i] =0
  • else:'Array[i]'에 가장 가까운 작은 값은 topof stackLS[i] =S.top()입니다.
  • 'Array[i]'를 S에 푸시
  • 오른쪽에 있는 모든 작은 요소 확인
• 처음에는 Array[]를 역 배열합니다. 이제 배열을 뒤집은 후 오른쪽이 작아지면 왼쪽이 작아집니다.
• 배열 RRS[]를 만들고 1단계와 2단계를 반복하여 RRS(LS 대신)를 채웁니다.
• 결과를 -1로 초기화하고 모든 elementArray[i]에 대해 다음을 수행합니다. Array[i]에 대해 오른쪽 작은 반전된 배열과 관련하여 RRS[n-i-1]return result =max(result, LS[i]-RRS[n-i-1])
에 저장됩니다.

예시

// C++ program to find the difference b/w left and
// right smaller element of every element in array
#include<bits/stdc++.h>
using namespace std;
// Shows function to fill left smaller element for every
// element of Array[0..n1-1]. These values are filled
// in SE1[0..n1-1]
void leftSmaller(int Array[], int n1, int SE1[]){
   // Build an empty stack
   stack<int>S1;
   // Visit all array elements
   // Calculate nearest smaller elements of every element
   for (int i=0; i<n1; i++){
      // Used to keep removing top element from S1 while the top
      // element is greater than or equal to Array[i]
      while (!S1.empty() && S1.top() >= Array[i])
      S1.pop();
      // Used to store the smaller element of current element
      if (!S1.empty())
         SE1[i] = S1.top();
      // It has been seen that if all elements in S were greater than Array[i]
      else
         SE1[i] = 0;
         // Used to push this element
         S1.push(Array[i]);
      }
   }
   // Shows function returns maximum difference b/w Left &
   // right smaller element
   int findMaxDiff(int Array[], int n1){
      int LS1[n1]; // To store left smaller elements
      // find left smaller element of every element
      leftSmaller(Array, n1, LS1);
      // Determine right smaller element of every element
      // first reverse the array and do the same process
      int RRS1[n1]; // Used to store right smaller elements in
      // reverse array
      reverse(Array, Array + n1);
      leftSmaller(Array, n1, RRS1);
      // Determine maximum absolute difference b/w LS1 & RRS1
      // In the reversed array right smaller for Array[i] is
      // stored at RRS1[n1-i-1]
   int result1 = -1;
   for (int i=0 ; i< n1 ; i++)
   result1 = max(result1, abs(LS1[i] - RRS1[n1-1-i]));
   // return maximum difference between LS1 & RRS1
   return result1;
}
// Driver program
int main(){
   int Array[] = {3, 5, 9, 8, 8, 10, 4};
   int n = sizeof(Array)/sizeof(Array[0]);
   cout << "Maximum diff : "
   << findMaxDiff(Array, n) << endl;
   return 0;
}

출력

Maximum diff : 4