在C ++中将数组分区为不相交的间隔

假设我们有一个数组A，我们必须将它分成左右两个子数组，以便-

• 左子数组中的每个元素都小于或等于右子数组中的每个元素。

• 左和右子数组为非空。

• 左子数组具有最小的可能大小。

我们必须找到这样的划分后的剩余长度。可以保证存在这样的分区。

因此，如果输入类似于[5,0,3,8,6]，则输出将为3，因为左数组将为[5,0,3]，右子数组将为[8,6]。

为了解决这个问题，我们将遵循以下步骤-

• n：= A的大小，创建大小为n的数组maxx

• minVal：= A的最后一个元素

• maxx [0]：= A [0]

• 当我在1到n – 1的范围内时

• maxx [i]：= A [i]和A [i – 1]的最大值

• ans：= A的大小– 1

• 因为我的范围是n – 1到1

• minVal：= minVal和A [i]的最小值

• 如果minVal> = max [i – 1]，则ans：= i

• 返回ans

示例

让我们看下面的实现以更好地理解-

#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]

输出结果

3