C++에서 정렬된 II를 만들기 위한 최대 청크

<시간/>

정수 배열 arr이 있다고 가정하고 배열을 몇 개의 파티션으로 분할하고 각 파티션을 개별적으로 정렬해야 합니다. 이제 그것들을 연결한 후에 우리는 하나의 정렬된 배열을 얻을 것입니다. 만들 수 있는 최대 파티션 수를 찾아야 합니까?

따라서 입력이 [3,2,4,5,5]와 같으면 출력은 [3,2], [4], [5], [5]와 같은 파티션을 만들 수 있으므로 4가 됩니다.

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

cnt :=1
n :=arr의 크기
n
크기의 배열 maxOfLeft를 정의합니다.
n
크기의 minOfRight 배열 정의
maxOfLeft[0] :=arr[0]
initialize i :=1의 경우, i
- maxOfLeft[i] :=maxOfLeft[i - 1] 및 arr[i]
  의 최대값
minOfRight[n - 1] =arr[n - 1]
initialize i :=n - 2의 경우 i>=0일 때 업데이트(i를 1만큼 감소), −
- minOfRight[i] :=minOfRight[i + 1] 및 arr[i]
  의 최소값
initialize i :=0의 경우, i
- minOfRight[i + 1]>=maxOfLeft[i]이면 -
  - (cnt를 1씩 증가)
반환 cnt

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

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int maxChunksToSorted(vector<int>& arr) {
      int cnt = 1;
      int n = arr.size();
      vector<int> maxOfLeft(n);
      vector<int> minOfRight(n);
      maxOfLeft[0] = arr[0];
      for (int i = 1; i < n; i++)
         maxOfLeft[i] = max(maxOfLeft[i - 1], arr[i]);
         minOfRight[n - 1] = arr[n - 1];
      for (int i = n - 2; i >= 0; i--)
         minOfRight[i] = min(minOfRight[i + 1], arr[i]);
      for (int i = 0; i < n - 1; i++) {
         if (minOfRight[i + 1] >= maxOfLeft[i])
         cnt++;
      }
      return cnt;
   }
};
main(){
   Solution ob;
   vector<int> v = {3,2,4,5,5};
   cout << (ob.maxChunksToSorted(v));
}

입력

{3,2,4,5,5}