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;
    }
}