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 <= 105
• 0 <= nums[i] < n
• nums 中的所有整数 互不相同
• nums 是范围 [0, n - 1] 内所有数字组成的一个排列

Problem: 775. 全局倒置与局部倒置

2、思路1

根据题意可知，局部倒置是全局倒置，全局倒置不一定是局部倒置，因此全局倒置的数量必然大于等于局部倒置。

当数组 nums 升序排列时不存在倒置情况，若将任意整数 k 置换到位置 i 就会出现倒置，二者差值大于 1 时必然会出现全局倒置的数量大于局部倒置。

3、Code

function isIdealPermutation(nums: number[]): boolean {
    for (let i = 0; i < nums.length; i++) {
        if (Math.abs(nums[i] - i) > 1) return false;
    }
    return true;
};

4、复杂度

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

5、执行结果

6、思路2

累计局部倒置数量 pc 和全局倒置数量 ac，当 nums[i] > nums[i + 1] 时 pc 加 1，当 nums[i] > i 时 ac 加 nums[i] - i，最后判断二者是否相等。其中有一种特殊情况：出现3个连续递减的数时全局倒置数量必定大于倒置数量。

这个思路正确性没有验证，完全是运气通过

7、Code

function isIdealPermutation(nums: number[]): boolean {
    let pc = 0, ac = 0;

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > nums[i + 1] && nums[i + 1] > nums[i + 2]) return false;

        if (nums[i] > nums[i + 1]) pc++;
        if (nums[i] > i) ac += nums[i] - i;
    }

    return pc === ac;
};

8、复杂度

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

9、执行结果

10、思路3

单调栈，耗时很长

11、Code

function isIdealPermutation(nums: number[]): boolean {
    let pc = 0, ac = 0, stack = [];

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > nums[i + 1]) pc++;

        if (!stack.length || stack.at(-1) > nums[i]) {
            ac += stack.length;
            stack.push(nums[i]);
        } else {
            const j = stack.findIndex(s => s < nums[i]);
            ac += j;
            stack.splice(j, 0, nums[i]);
        }
    }

    return pc === ac;
};

12、复杂度

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n)$

13、执行结果