775.全局倒置与局部倒置

问题

数组 $A$ 是 $[0,1,...,N-1]$ 的一种排列，$N$ 是数组 $A$ 的长度。全局倒置指的是 $i,j$ 满足 $0<=i<j<N$ 并且 $[i]>A[j]$ ，局部倒置指的是 $i$ 满足 $0<=i<N$ 并且 $A[i]>A[i+1]$ 。

当数组 $A$ 中全局倒置的数量等于局部倒置的数量时，返回 $true$ 。

示例 1:

输入: $A=[1,0,2]$ 输出: $true$ 解释: 有 1 个全局倒置，和 1 个局部倒置。

示例 2:

输入: $A=[1,2,0]$ 输出: false 解释: 有 2 个全局倒置，和 1 个局部倒置。

注意:

• $A$ 是 $[0,1,...,A.length-1]$ 的一种排列
• $A$ 的长度在 $[1,5000]$之间
• 这个问题的时间限制已经减少了。

解法

一开始想法比较简单，既然是求逆序对的数量，那么双层for循环一个$O(n^2)$的解法就完了。但是第三项注意事项中说了时间限制已经减少，所以毫无意外的超时了。 此时考虑逆序对的性质，全局倒置一定是局部倒置。 对一个$[0,1,...,A.length-1]$的排序数组而言，索引$i$，如果满足$abs(A[i]-i)<=1$,那么，说明$i$只是左移或者右移了一位（或者没变），全局倒置与局部倒置至少同时加一（或者保持不变），仍然满足条件；如果$abs(A[i]-i)>=2$,那么，说明$A[i]$至少左移或者右移了两位，意味着右边至少有两个比自己小的数（或者左边必然有来2个比自己大且不相邻的数，其中至少一个不相邻）局部（必然<）全局所以造成一定不等，此时不满足条件，直接返回false。

代码

java

class Solution {
    public boolean isIdealPermutation(int[] A) {
        if (A.length <3) {
            return true;
        }
        for (int i = 0; i < A.length; i++) {
            if (Math.abs(A[i] - i) >= 2) {
                return false;
            }
        }
        return true;
    }
}