问题

数组 \(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;
    }
}