LeetCode 775. Global and Local Inversions

You are given an integer array nums of length n which represents a permutation of all the integers in the range [0, n - 1].

The number of global inversions is the number of the different pairs (i, j) where:

• 0 <= i < j < n

• nums[i] > nums[j]

The number of local inversions is the number of indices i where:

• 0 <= i < n - 1

• nums[i] > nums[i + 1]

Return true if the number of global inversions is equal to the number of local inversions.

Example 1:

Input: nums = [1,0,2]

Output: true

Explanation: There is 1 global inversion and 1 local inversion.

Example 2:

Input: nums = [1,2,0]

Output: false

Explanation: There are 2 global inversions and 1 local inversion.

这里面local的就一定是global的，所以如果要返回false就是当存在num[i]>num[j];

同时i+2<=j;

我们保存一个max，让max去跟目前的j去比对，即可；

Constraints:

• n == nums.length

• 1 <= n <= 105

• 0 <= nums[i] < n

• All the integers of nums are unique.

• nums is a permutation of all the numbers in the range [0, n - 1].

Runtime: 1 ms, faster than 100.00% of Java online submissions for Global and Local Inversions.

Memory Usage: 51.6 MB, less than 70.61% of Java online submissions for Global and Local Inversions.