在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