C++의 전역 및 로컬 반전

[0, 1, ..., N - 1]의 순열 A가 있다고 가정합니다. 여기서 N은 A의 길이입니다. 이제 (전역) 역전의 수는 0 <=i <인 i A[j]. 그리고 로컬 반전의 수는 0 <=i A[i+1]인 i의 수입니다. 전역 반전 수가 로컬 반전 수와 동일한 경우에만 true를 반환해야 합니다. 따라서 입력이 [1,0,2]와 같으면 로컬 반전과 전역 반전이 하나만 있으므로 true를 반환합니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• maxVal :=-1, n :=A의 크기
• 0 ~ n – 3 범위의 i에 대해
  • 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