C++의 배열에서 다음 작은 것보다 큰 것 찾기

<시간/>

이 문제에서는 n개의 정수 값으로 구성된 배열 arr[]이 제공됩니다. 우리의 임무는 배열에서 다음 큰 것 중 다음 작은 것을 찾는 것입니다.

문제 설명 - 배열의 현재 요소보다 큰 요소를 찾은 다음 이 큰 요소보다 작은 배열의 요소를 찾습니다. 배열에 다음으로 작거나 큰 요소가 없으면 -1을 반환합니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

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

출력

{3, 3, 1, 1, -1, -1}

설명

다음으로 큰 요소의 배열 :{8, 8, 9, 9, -1, -1} 배열의 가장 큰 요소는 9이고 마지막 요소는 1이므로 다음으로 큰 요소가 없습니다.

다음으로 큰 요소 중 다음으로 작은 요소의 배열:{3, 3, 1, 1, -1, -1}

솔루션 접근 방식

문제에 대한 간단한 해결책은 배열을 반복하고 배열의 각 요소에 대해

배열에서 다음으로 큰 요소를 찾습니다.
나머지 배열에서 이 큰 요소보다 작은 요소를 찾습니다.

이 솔루션은 작업을 수행하지만 시간 복잡성은 O(n² ).

더 나은 솔루션 문제는 요소의 스택과 인덱스를 사용하는 것일 수 있습니다.

현재 요소의 다음으로 크고 작은 요소의 인덱스를 배열 이름 nextGreater[] 및 nextSmaller[]의 두 배열에 저장합니다. 이것은 배열 nextGreater가 현재 요소의 다음으로 큰 요소의 인덱스를 저장함을 의미합니다. 예를 들어, nextGreater[i]는 다음으로 큰 요소의 인덱스를 가지며 이는 arr[nextGreater[i]]가 됩니다. nextSmaller[]도 마찬가지입니다.

따라서 배열의 다음으로 큰 요소의 다음으로 작은 요소에 액세스합니다. nextGreater[i]에서 인덱스의 다음으로 작은 요소를 찾습니다. 이것은 필요한 요소의 인덱스를 제공합니다. 즉, 필수 요소는 arr[nextSmaller[nextGreater[i]]]입니다.

요소를 찾기 위해 나머지 하위 배열의 요소를 저장할 스택 데이터 구조를 사용합니다. 더 큰 요소를 찾기 위해 함수가 작동하는 방식은 다음과 같습니다.

=> 마지막 i -> n-1에서 0까지 배열을 순회합니다.
=> 스택이 비어 있지 않고 스택의 맨 위가 currentelement보다 작으면 -> pop S, 더 큰 요소를 찾거나 스택이 비워질 때까지 이 작업을 수행합니다.
=> 스택이 비어 있으면 -> 가능한 더 큰 요소가 없으면 -1,nextGreater[i] =-1을 저장합니다.
=> else -> 다음으로 큰 요소가 스택의 맨 위에 있고 스택의 맨 위에 저장됩니다. nextGreater[i] =stack.top().
=> 현재 요소를 스택으로 푸시, stack.push()

동일한 방법을 사용하여 배열의 현재 요소에 대해 다음으로 작은 요소를 찾을 수 있습니다. 그리고 일단 우리는 둘 다의 인덱스를 찾았습니다. 이 인덱스를 사용하여 배열에서 필요한 요소를 찾을 수 있습니다.

우리 솔루션의 작동을 설명하는 프로그램

예시

#include<bits/stdc++.h>
using namespace std;
void findNextGreater(int arr[], int n, int next[]) {
   stack<int> nextGreater;
   int i = n-1;
   while(i >= 0) {
      while (!nextGreater.empty() && arr[nextGreater.top()] <= arr[i] )
         nextGreater.pop();
      if (!nextGreater.empty())
         next[i] = nextGreater.top();
      else
         next[i] = -1;
      nextGreater.push(i);
      i--;
   }
}
void findNextSmaller(int arr[], int n, int next[]) {
   stack<int> nextSmaller;
   int i = n-1 ;
   while(i >= 0){
      while (!nextSmaller.empty() && arr[nextSmaller.top()] >= arr[i])
         nextSmaller.pop();
      if (!nextSmaller.empty())
         next[i] = nextSmaller.top();
      else
         next[i] = -1;
      nextSmaller.push(i);
      i -- ;
   }
}
void findNextSmallerofNextGreaterElemenetArray(int arr[], int n) {
   int nextGreaterIndex[n];
   int nextSmallerIndex[n];
   findNextGreater(arr, n, nextGreaterIndex);
   findNextSmaller(arr, n, nextSmallerIndex);
   for (int i=0; i< n; i++){
      if (nextGreaterIndex[i] != -1 && nextSmallerIndex[nextGreaterIndex[i]] != -1)
         cout<<arr[nextSmallerIndex[nextGreaterIndex[i]]]<<"\t";
      else
         cout<<"-1"<<"\t";
   }
}
int main(){
   int arr[] = {4, 2, 8, 3, 9, 1};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<"All next smaller of next greater elements of the array are ";
   findNextSmallerofNextGreaterElemenetArray(arr, n);
   return 0;
}

출력

All next smaller of next greater elements of the array are 3 3 1 1 -1 -1