LeetCode 775. 全局倒置与局部倒置
题目描述
题意分析
数组是
0到n-1的一个排列。全局倒置是满足i < j且nums[i] > nums[j]的下标对，局部倒置额外要求j = i+1。判断这两种倒置数量是否相等。
解法：后缀最小值判定
核心思路
[!blue]
每个局部倒置都是全局倒置，所以全局倒置数等于局部倒置数加上非相邻倒置数。两者相等，当且仅当不存在下标相差至少 2 的倒置，无需真的统计两种数量。
对固定左端
i，允许的非相邻右端为j >= i+2。这个后缀中只要有一个值小于nums[i]就存在反例，等价于nums[i] > min(nums[i+2...n-1])；若连最小值都不小于当前值，后缀中的其他值也不会构成倒置。从右向左扫描，用
minSuf保存所需后缀的最小值。当前位置由右向左移动一格时，只新增一个更靠左的候选nums[i+2]，因此先将它并入minSuf，再与nums[i]比较。更新后覆盖范围恰好是[i+2, n-1]，不会误把相邻位置i+1算入。扫描从
n-3开始，因为更靠右的位置不可能再有距离至少 2 的右端；任意一轮发现反例立即返回false，全部检查通过则返回true。长度不足 3 时不存在非相邻下标对，两种数量必然相等。
解题步骤
- 长度不足三时直接返回 true。
- 从倒数第三个位置开始反向扫描。
- 将距离当前至少两位的后缀最小值更新完整。
- 发现当前值大于该最小值就返回 false，否则最终返回 true。
代码实现
class Solution {
public boolean isIdealPermutation(int[] nums) {
int n = nums.length;
if (n < 3) {
return true;
}
int minSuf = nums[n - 1];
for (int i = n - 3; i >= 0; i--) {
// 后缀从相隔两位的位置开始，专门查找非相邻倒置。
minSuf = Math.min(minSuf, nums[i + 2]);
if (nums[i] > minSuf) {
return false;
}
}
return true;
}
}
func isIdealPermutation(nums []int) bool {
n := len(nums)
if n < 3 {
return true
}
minSuf := nums[n-1]
for i := n - 3; i >= 0; i-- {
// 后缀从相隔两位的位置开始，专门查找非相邻倒置。
if nums[i+2] < minSuf {
minSuf = nums[i+2]
}
if nums[i] > minSuf {
return false
}
}
return true
}
复杂度分析
- 时间复杂度：$O(n)$，每个可能作为非相邻倒置左端的位置只检查一次。
- 空间复杂度：$O(1)$，只维护一个后缀最小值和循环下标。
关键点总结
[!green]
- 无需真的计算两种倒置数量。
- 后缀从 i+2 开始，专门检查非相邻倒置。
- 只需找到一个额外全局倒置即可否定。
易错点总结
[!yellow]
- 从 i+1 开始维护最小值：会把允许的局部倒置当成反例。
- 只比较 nums[i] 与 nums[i+2]：更远位置也可能更小。
- 维护后缀最大值：无法判断是否存在更小的远端元素。
- 比较后才纳入
nums[i+2]：会漏掉与当前位置恰好相隔两位的候选，只检查到更远的后缀。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 剑指 Offer 51. 数组中的逆序对 | 困难 | 全局倒置就是普通逆序对，本题要判断是否所有逆序都只发生在相邻位置。 |
| 315. 计算右侧小于当前元素的个数 | 困难 | 右侧较小值数量之和可得到全局倒置数，本题可利用排列约束直接检测非局部倒置。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！