C++でのグローバルおよびローカルの反転

[0、1、...、N --1]の順列Aがあるとします。ここで、NはAの長さです。ここで、（グローバル）反転の数はi A[j]。また、ローカル反転の数は、0 <=iA [i+1]のiの数です。グローバル反転の数がローカル反転の数と等しい場合にのみ、trueを返す必要があります。したがって、入力が[1,0,2]の場合、ローカル反転とグローバル反転が1つしかないため、trueを返します。

これを解決するには、次の手順に従います-

• maxVal：=-1、n：=Aのサイズ
• 0からn–3の範囲のiの場合
  • maxVal：=A[i]とmaxValの最大値
  • maxVal> A [i + 2]の場合、falseを返します
• trueを返す

理解を深めるために、次の実装を見てみましょう-

例

#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