C ++中的全局和局部反转
假设我们有一个[0，1，...，N-1]的置换A，其中N是A的长度。现在（全局）求反的数目是i<j的数目，0<=i<j<N且A[i]>A[j]。局部反演的数量是0<=i<N且A[i]>A[i+1]的i的数量。当且仅当全局反转的数量等于局部反转的数量时，我们才必须返回true。因此，如果输入像[1,0,2]，则返回true，因为只有一个局部反演和一个全局反演。
为了解决这个问题，我们将遵循以下步骤-
maxVal：=-1，n：=A的大小
对于i，范围为0至n–3
maxVal：=A[i]和maxVal的最大值
如果maxVal>A[i+2]，则返回false
返回真
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isIdealPermutation(vector<int>& A) {
int maxVal = -1;
int n = A.size();
for(int i = 0; i < n - 2; i++){
maxVal = max(A[i], maxVal);
if(maxVal > A[i + 2])
return false;
}
return true;
}
};
main(){
vector<int> v = {1,0,2};
Solution ob;
cout << (ob.isIdealPermutation(v));
}输入值
[1,0,2]
输出结果
1