LeetCode_数学归纳_中等_775.全局倒置与局部倒置

1.题目

给你一个长度为 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。

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/global-and-local-inversions

2.思路

（1）暴力穷举法
暴力穷举法比较容易想到，即使用两层 for 循环来统计全局倒置的数目和局部倒置的数目，遍历结束后，如果两者相等则返回 true，否则返回 false。但是该方法的时间复杂度为 O(n²)，在 LeetCode 中提交会出现“超出时间限制”的提示！

另外还有一种类似的思路（不过也超时了）：由题意可知，一个局部倒置一定是一个全局倒置，因此如果数组 nums 中存在某个全局倒置，但又不是局部倒置，那么说明两者的数量一定不想等，此时直接返回 false 即可。

（2）维护最小后缀值
思路参考本题官方题解。

① 承接（1）中的第二种思路，要想判断某个倒置为全局倒置，但又不是局部倒置，即需判断 nums[i] > nums[j]，i + 1 < j，这与判断 nums[i] > min(nums[i + 2], nums[i + 3], …, nums[nums.length - 1]) 一致。

② 所以只需维护一个变量 minSuffix，使其记录数组 nums 的最小后缀值即可，其初始值为 nums[nums.length - 1]。

③ 然后再倒序遍历 nums[0…nums.length - 3] 中的每一个 i，如果存在某个 i，使得 nums[i] > minSuffix 成立，则直接返回 false。如果遍历结束后仍未找到这样的 i，那么返回 true 即可。

（3）数学归纳证明
思路参考本题官方题解。

3.代码实现（Java）

//思路1————暴力穷举法
class Solution {
    public boolean isIdealPermutation(int[] nums) {
    	// global 记录全局倒置的数目
        int global = 0;
        // local 记录局部倒置的数目
        int local = 0;
        int length = nums.length;
        //暴力穷举法来统计 global 和 local
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                if (nums[i] > nums[j]) {
                    if (j == i + 1) {
                        local++;
                    }
                    global++;
                }
            }
        }
        return global == local;
    }
}

//另一种类似的思路
class Solution {
    public boolean isIdealPermutation(int[] nums) {
        int notLocal = 0;
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            for (int j = i + 2; j < length; j++) {
            	//如果 nums[i] > nums[j]，那么则说明存在某个全局倒置，但又不是局部倒置
                if (nums[i] > nums[j]) {
                    return false;
                }
            }
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

//思路2————维护最小后缀值
class Solution {
    public boolean isIdealPermutation(int[] nums) {
        int length = nums.length;
        // minSuffix 记录数组 nums 的后缀最小值，初始值为 nums[length - 1]
        int minSuffix = nums[length - 1];
        for (int i = length - 3; i >= 0; i--) {
        	//如果 nums[i] > minSuffix，那么则说明存在某个全局倒置，但又不是局部倒置
            if (nums[i] > minSuffix) {
                return false;
            }
            //更新 minSuffix
            minSuffix = Math.min(minSuffix, nums[i + 1]);
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

//思路3————数学归纳证明
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;
    }
}
1
2
3
4
5
6
7
8
9
10
11