不二

问题描述

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.

问题分析

从题意可以看出，每存在一个local inversion，就必定存在一个global inversion；反过来则不一定；

要想让global inversion和local inversion数量刚好相等，要么两者均为0，要么对于global inversion，不存在跨local的情况。因此我们的做法如下：

1. 首先遍历A，获得对应数字的下标
2. 对于i从1到N-1依次进行如下判断：
   1. 维护变量maxpos，用来表示i-1在A中的最大下标
   2. 如果m[i]大于maxpos，说明i与i-1之间不存在inversion，忽略即可
   3. 如果m[i]小于maxpos-1，说明i与i-1之间存在inversion，且跨度超过了local；如果存在这种情况，直接返回结果false
3. 如果遍历完，没有中途return，说明符合条件，返回true
   
   

示例代码

func isIdealPermutation(A []int) bool {
	m := make(map[int]int)
	for i := 0; i < len(A); i++ {
		m[A[i]] = i
	}
	maxpos := m[0]
	for i := 1; i < len(A); i++ {
		if m[i-1] > maxpos {
			maxpos = m[i-1]
		}
		if m[i] < maxpos-1 {
			return false
		}
	}

	return true
}

优化解法

提交AC后，在评论区，看到更为优化的解法，基于以下原来：

对于A中的每一个i，其可能的摆放位置只有3种：A[i], A[i-1], A[i+1]，因此如果A[i]与i的差值绝对值超过了1，那么就可以认为存在跨local的情况，返回false

解法如下：

func isIdealPermutationV2(A []int) bool {
	for i := 0; i < len(A); i++ {
		if (A[i]-i) > 1 || (A[i]-i) < -1 {
			return false
		}
	}
	return true
}

原题链接

Global And Local Inversions