题目地址: https://leetcode.com/problems/global-and-local-inversions/description/
题目描述：
Wehave some permutation A of [0, 1, ..., N - 1], where N is the length of A.
Thenumber of (global) inversions is the number of i < j with 0 <= i < j < N and A[i] > A[j].
Thenumber 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:
1、 Awillbeapermutationof[0,1,...,A.length-1].；
2、 Awillhavelengthinrange[1,5000].；
3、 Thetimelimitforthisproblemhasbeenreduced.；
题目大意
如果存在i < j with 0 <= i < j < N and A[i] > A[j]，称之为一个全局翻转。 如果存在0 <= i < N and A[i] > A[i+1]，称之为一个局部翻转。 判断一个由0～N - 1组成的一个乱序数组中，全局翻转的个数与局部翻转的个数是否相等。
解题方法
首先当j = i + 1时，可以看出，一个局部翻转就是一个全局翻转。那么如果要使得局部翻转和全局翻转的个数相等，那么必须要求全局翻转也是一个局部翻转。所以，对于任意的j > i + 1，不能存在A[i] > A[j]，即需要满足A[i] <= A[j].
从上面的关系可以看出，我们必须使max(A[:i]) <= A[i + 2]。
最坏情况下的时间复杂度是O(N)，空间复杂度是O(1)。
class Solution(object):
def isIdealPermutation(self, A):
"""
:type A: List[int]
:rtype: bool
"""
cmax = 0
for i in range(len(A) - 2):
cmax = max(cmax, A[i])
if cmax > A[i + 2]:
return False
return True
1 2 3 4 5 6 7 8 9 10 11 12
上面的想法并没有好好的利用题目给出的数字是0N-1这个条件。所以我们继续思考，如果原来的顺序是0N-1，那么如何交换两个数字才能满足局部翻转的个数等于全局翻转呢？答案当然是只翻转相邻的两个元素。否则会构造出来一个不是局部翻转的全剧翻转。所以i的位置上只能放A[i-1],A[i],A[i+1]。
class Solution(object):
def isIdealPermutation(self, A):
"""
:type A: List[int]
:rtype: bool
"""
for i, a in enumerate(A):
if abs(a - i) > 1:
return False
return True
1 2 3 4 5 6 7 8 9 10
参考资料：
https://leetcode.com/problems/global-and-local-inversions/discuss/113644/Easy-and-Concise-Solution-C++JavaPython
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发