C++에서 배열을 분리된 간격으로 분할

<시간/>

배열 A가 있다고 가정하고 왼쪽과 오른쪽 두 개의 하위 배열로 분할해야 다음과 같이 됩니다. -

왼쪽 부분배열의 모든 요소는 오른쪽 부분배열의 모든 요소보다 작거나 같습니다.
왼쪽 및 오른쪽 하위 배열이 비어 있지 않습니다.
왼쪽 하위 배열은 가능한 가장 작은 크기를 갖습니다.

우리는 이러한 분할 후에 왼쪽의 길이를 찾아야 합니다. 그러한 파티션이 존재한다는 것은 보장됩니다.

따라서 입력이 [5,0,3,8,6]과 같으면 왼쪽 배열이 [5,0,3]이 되고 오른쪽 하위 배열이 [8,6]이 되기 때문에 출력이 3이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=A의 크기, n 크기의 배열 maxx 생성
minVal :=A의 마지막 요소
maxx[0] :=A[0]
범위 1에서 n – 1까지의 i에 대해
- maxx[i] :=A[i] 및 A[i – 1]의 최대
ans :=A – 1의 크기
범위 n – 1에서 1까지의 i에 대해
- minVal :=minVal 및 A[i]의 최소값
- minVal>=max[i – 1]이면 ans :=i
반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int partitionDisjoint(vector <int>& A) {
      int n = A.size();
      vector <int> maxx(n);
      int minVal = A[n - 1];
      maxx[0] = A[0];
      for(int i = 1; i < n; i++){
         maxx[i] = max(A[i], maxx[i - 1]);
      }
      int ans = A.size() - 1;
      for(int i = n - 1; i >= 1; i--){
         minVal = min(minVal, A[i]);
         if(minVal >= maxx[i - 1]){
            ans = i;
         }
      }
      return ans;
   }
};
main(){
   vector<int> v1 = {5,0,3,8,6};
   Solution ob;
   cout << (ob.partitionDisjoint(v1));
}

입력

[5,0,3,8,6]