0775. Global and Local Inversions

题目信息

题号:

0775

难度:

Medium

主题:

排列、逆序对、相邻关系

原题:

LeetCode 0775

重点:

全局逆序对允许任意 i < j,局部逆序只统计相邻下标;输入是 0 至 n - 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],则相邻位置 i 与 i + 1 构成一个局部逆序。

请判断全局逆序对的总数是否恰好等于局部逆序的总数。1 <= n <= 10^5,所有元素互不相同且位于 [0, n - 1]。

自建示例

存在非局部的全局逆序:

输入:nums = [2,0,1,3]
输出:false
解释:全局逆序对为 (2,0) 和 (2,1),共 2 个;局部逆序只有相邻的 (2,0),共 1 个,因此数量不相等。

全部逆序都发生在相邻位置:

输入:nums = [0,2,1,3]
输出:true
解释:唯一的全局逆序对是相邻的 (2,1),它同时也是唯一的局部逆序。