0775. Global and Local Inversions¶
题目信息¶
- 题号:
0775
- 难度:
Medium
- 主题:
排列、逆序对、相邻关系
- 原题:
- 重点:
全局逆序对允许任意
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),它同时也是唯一的局部逆序。