图解LeetCode——775. 全局倒置与局部倒置（难度：中等）

一、题目

给你一个长度为 n 的整数数组 nums ，表示由范围 [0, n - 1] 内所有整数组成的一个排列。 全局倒置 的数目等于满足下述条件不同下标对 (i, j) 的数目：

• • 0 <= i < j < n
• • nums[i] > nums[j]

局部倒置 的数目等于满足下述条件的下标 i 的数目：

• • 0 <= i < n - 1
• • nums[i] > nums[i + 1]

当数组 nums 中 全局倒置 的数量等于 局部倒置 的数量时，返回 true ；否则，返回 false 。

二、示例

2.1> 示例 1：

【输入】nums = [1,0,2] 【输出】true 【解释】有 1 个全局倒置，和 1 个局部倒置。

2.2> 示例 2：

【输入】nums = [1,2,0] 【输出】false 【解释】有 2 个全局倒置，和 1 个局部倒置。

提示：

• • n == nums.length
• • 1 <= n <= 5000
• • 0 <= nums[i] < n
• • nums 中的所有整数 互不相同
• • nums 是范围 [0, n - 1] 内所有数字组成的一个排列

三、解题思路

3.1> 根据前缀的最大值来判断

根据题目描述，我们可以得到如下结论：

如果是局部倒置，那么一定就是全局倒置。所以，全局倒置是包含局部倒置的。

那么我们就可以将解题视角放在非局部倒置的全局倒置上。换句话说，也就是—— 非相邻数字是否满足递增。 具体操作如下图所示：

3.2> 根据偏移的差值来判断

由于题目中已经给出了如下一个关键条件：

数组nums长度为n，并且数字是由0到n-1构成的。

所以，就可以通过nums[i]-i计算出i位置的元素与有序后的位置之间的差值：

【差值等于0】表示元素i所在的位置就是排序后的位置。 【差值等于1】表示元素1所在的位置向前1位或向后1位。 【其他情况】表示元素所在位置偏差大于1位，也就是出现了全局倒置并且非局部倒置的情况。

具体操作如下图所示：

四、代码实现

4.1> 根据前缀的最大值来判断

class Solution {
    public boolean isIdealPermutation(int[] nums) {
        int max = nums[0];
        for (int i = 2; i < nums.length; i++) {
            if (nums[i] < max) return false;
            max = Math.max(max, nums[i - 1]);
        }
        return true;
    }
}

4.2> 根据偏移的差值来判断

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