We have some permutation A of [0, 1, ..., N - 1], where N is the length of A.
The number of (global) inversions is the number of i < j with 0 <= i < j < N and A[i] > A[j].
The number of local inversions is the number of i with 0 <= i < N and A[i] > A[i+1].
Return true if and only if the number of global inversions is equal to the number of local inversions.
Example 1:
Input: A = [1,0,2]
Output: true
Explanation: There is 1 global inversion, and 1 local inversion.
Example 2:
Input: A = [1,2,0]
Output: false
Explanation: There are 2 global inversions, and 1 local inversion.
Note:
A will be a permutation of [0, 1, ..., A.length - 1].
A will have length in range [1, 5000].
The time limit for this problem has been reduced.
Code in Python:
def isIdealPermutation(self, A):
"""
:type A: List[int]
:rtype: bool
"""
for i in range(len(A)):
if abs(A[i]-i) > 1:
return False
return True
注解：
global=local的情况：升序排列的list，每个元素变动位置的范围大小不超过1，如：1 2 3 4 5 6 7 → 1 3 2 5 4 7 6，是可以的。
Discuss地址：
https://discuss.leetcode.com/category/1743/global-and-local-inversions
