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