775. 全局倒置与局部倒置（难度：中等）

手机游戏开发者 · 2024-9-8 13:58:31

标题形貌：https://leetcode.cn/problems/global-and-local-inversions/

标题形貌：

给你一个长度为 n 的整数数组 nums ，表示由范围 [0, n - 1] 内全部整数构成的一个分列。
全局倒置 的数量便是满足下述条件差异下标对 (i, j) 的数量：

0 <= i < j < n
nums > nums[j]
局部倒置 的数量便是满足下述条件的下标 i 的数量：
0 <= i < n - 1
nums > 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 <= 105

0 <= nums < n

nums 中的全部整数 互不雷同

nums 是范围 [0, n - 1] 内全部数字构成的一个分列

解法：后缀最小值

根据标题意思可知，局部导致肯定是全局导致，而全局导致不肯定是局部导致。那我们只需要找到是否存在局部导致好坏全局导致的，即 i < j - 1，num > num[j]的情况。
我们可以从后往前遍历，盘算后缀的最小值，判断当前遍历的元素，是否小于后缀最小值即可。

775. 全局倒置与局部倒置（难度：中等）

所属分类: 问答交流

新帖推荐: 30日

推荐作品