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]``。 自建示例 -------- 存在非局部的全局逆序: .. code-block:: text 输入:nums = [2,0,1,3] 输出:false 解释:全局逆序对为 (2,0) 和 (2,1),共 2 个;局部逆序只有相邻的 (2,0),共 1 个,因此数量不相等。 全部逆序都发生在相邻位置: .. code-block:: text 输入:nums = [0,2,1,3] 输出:true 解释:唯一的全局逆序对是相邻的 (2,1),它同时也是唯一的局部逆序。