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

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个数组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

以上是 在C ++中将数组分区为不相交的间隔 的全部内容， 来源链接： utcz.com/z/327115.html

回到顶部