What is the main difference between global and local inversions in this problem?

A local inversion is always a global inversion where indices are adjacent, but a global inversion can span non-adjacent indices, which is critical to detect in this problem.

Why is a one-pass solution preferred for Global and Local Inversions?

It leverages the array plus math pattern to maintain a running maximum, avoiding costly nested iteration and reducing time complexity to O(n).

Can this approach handle large arrays up to 105 elements?

Yes, because it scans the array once and uses O(1) extra space, it scales efficiently for large n within the problem constraints.

Is counting local and global inversions separately necessary?

No, direct counting is inefficient; using maximum tracking detects any global inversion that is not local, which suffices for correctness.

How does the permutation property of nums simplify the solution?

Since nums is a permutation of 0 to n - 1, mathematical bounds ensure that checking the maximum before index i - 2 is enough to detect extra global inversions.

#775

Medium

auto_awesome数组·数学

LeetCode 题解工作台

全局倒置与局部倒置

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

数组数学

题目描述

给你一个长度为 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] 内所有数字组成的一个排列

lightbulb

解题思路

方法一：维护前缀最大值

根据题意，我们可以发现，一个数组中的局部倒置一定是全局倒置，但是全局倒置不一定是局部倒置。也就是说，全局倒置的数量一定大于等于局部倒置的数量。

因此，我们枚举每个数 $nums[i]$ ，其中 $2 \leq i \leq n - 1$ ，维护前缀数组 $nums[0,..i-2]$ 中的最大值，记为 $mx$ 。如果存在 $mx$ 大于 $nums[i]$ ，则说明全局倒置的数量大于局部倒置的数量，返回 false 即可。

遍历结束后，返回 true。

时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ 。其中 $n$ 为数组 nums 的长度。

1

2

3

4

5

6

7

8

class Solution:
    def isIdealPermutation(self, nums: List[int]) -> bool:
        mx = 0
        for i in range(2, len(nums)):
            if (mx := max(mx, nums[i - 2])) > nums[i]:
                return False
        return True

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Checks if you understand the distinction between local and global inversions.
question_mark
Wants you to optimize beyond brute-force nested loops.
question_mark
Seeks recognition of permutation constraints and mathematical bounds for array positions.

warning

常见陷阱

外企场景

error
Counting inversions directly with nested loops causes timeouts for large arrays.
error
Ignoring that local inversions are always global inversions can lead to false negatives.
error
Not considering positions two or more apart for global inversions results in incorrect answers.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Determine the number of global inversions minus local inversions instead of boolean check.
arrow_right_alt
Handle arrays that are not strict permutations, requiring extra validation.
arrow_right_alt
Extend to k-local inversions, where an inversion spans at most k indices.

help

常见问题

外企场景

继续练习

#781 森林中的兔子 #782 变为棋盘 #789 逃脱阻碍者