LeetCode 775. 全局倒置与局部倒置

2022-03-07 HGNULB 约 12 分钟

文章信息 6 个分类 2 个标签

分类

题目描述

✅ 775. 全局倒置与局部倒置

题意分析

给定一个由 $0$ 到 $n-1$ 构成的排列 nums，判断它的全局倒置数是否等于局部倒置数。全局倒置指所有满足 $i < j$ 且 $nums[i] > nums[j]$ 的下标对；局部倒置指其中 $j = i + 1$ 的那些，也就是相邻的一对逆序。

读题的第一个关键动作是意识到：局部倒置是全局倒置的子集。每一个局部倒置 $(i, i+1)$ 天然也是一个全局倒置，所以全局数永远不小于局部数。因此「两者相等」等价于「不存在任何非局部的全局倒置」，也就是不存在下标对 $(i, j)$ 满足 $j \ge i + 2$ 且 $nums[i] > nums[j]$。这个转化把一道计数题变成了一道存在性判定题，计数的负担瞬间消失——不需要真的算出两个数字，只需要判断有没有反例。

第二个信号来自「排列」这个前提。数组恰好是 $0$ 到 $n-1$ 的一个重排，元素互不相同，所以不用考虑相等带来的边界歧义（$nums[i] > nums[j]$ 与 $nums[i] \ge nums[j]$ 在这里只差严格性，而相等只可能发生在 $i = j$）。

约束是 $1 \le n \le 10^5$。这个规模排除了 $O(n^2)$ 的两两枚举（$10^{10}$ 次比较），也提示答案应该是一次线性扫描。归并排序数逆序对是 $O(n \log n)$ 的，能过但完全没必要——我们要的是「有没有」而不是「有多少个」。

边界方面：$n = 1$ 时没有任何下标对，两个计数都是 0，答案为真；$n = 2$ 时唯一的下标对 $(0,1)$ 既是全局也是局部，无论顺序如何都相等，答案仍为真。只有 $n \ge 3$ 才可能出现跨度至少为 2 的下标对，判定逻辑从这里才真正开始。

解法：后缀最小值判定

核心思路

最朴素的想法是分别数出两种倒置的个数再比较：局部倒置一次扫描就能数完，全局倒置需要两两枚举，$O(n^2)$ 在 $10^5$ 的规模下必然超时。就算换成归并排序或树状数组把全局计数降到 $O(n \log n)$，仍然是在做一件多余的事——我们并不关心具体数量。

瓶颈找到了：计数太贵，而判定很便宜。根据题意分析里的转化，只要能回答「是否存在 $j \ge i+2$ 使得 $nums[i] > nums[j]$」就够了。把这个存在性条件按 $i$ 拆开：对每个固定的 $i$，它等价于

$nums[i] > \min{nums[i+2],\ nums[i+3],\ \dots,\ nums[n-1]}$

也就是说，只需要拿 $nums[i]$ 和「从 $i+2$ 开始的后缀最小值」比一次。原本对每个 $i$ 要遍历所有更靠后的位置，现在被压缩成一次比较——因为若 $nums[i]$ 连后面最小的那个都不超过，它就不可能超过后面的任何一个。

于是显式写下要维护的状态：扫描到下标 $i$ 时，变量 $minSuf$ 等于 $\min{nums[i+2], \dots, nums[n-1]}$，即从 $i+2$ 到末尾这段后缀的最小值。 这是整段代码的不变量，所有正确性都系于它。

要让 $minSuf$ 满足这个定义，扫描方向必须是从右往左。因为后缀最小值只有在已经看过右边全部元素后才能确定；从左往右扫无法在 $O(1)$ 内维护它。

起点也随之确定：$i$ 从 $n-3$ 开始（这是第一个存在 $i+2$ 的下标），此时后缀 $[i+2, n-1]$ 恰好只含 $nums[n-1]$ 一个元素，所以 $minSuf$ 的初值就是 $nums[n-1]$。

每轮的操作顺序很讲究：先用 $nums[i+2]$ 更新 $minSuf$，再拿 $nums[i]$ 去比较。从 $i+1$ 移到 $i$ 时，后缀的左边界从 $i+3$ 扩到了 $i+2$，新纳入的元素恰好是 $nums[i+2]$，所以先合并它才能让不变量在比较发生前成立。顺序反了就会用「$i+1$ 那一轮的后缀」去判断 $i$，漏掉 $nums[i]$ 与 $nums[i+2]$ 这一对，而这恰恰是最容易出问题的一对。

一旦发现 $nums[i] > minSuf$，就找到了一个非局部的全局倒置，立即返回假；扫完全程都没发现，返回真。

顺便说一句这道题广为流传的另一种判据：$ nums[i] - i \le 1$ 对所有 $i$ 成立。它的推导是，若某个元素偏离自己的排序位置超过 1，就必然与至少两个元素形成跨度不小于 2 的倒置。这个写法更短，但它依赖「输入是 $0$ 到 $n-1$ 的排列」这一强假设；而后缀最小值的判定只依赖倒置的定义本身，对任意数组都成立，可迁移性更好，也更容易在面试中当场论证。

解题步骤

第一步，若 $n < 3$ 直接返回真。 为什么：跨度至少为 2 的下标对需要 $j \ge i+2$，$n < 3$ 时根本不存在这样的一对，全局与局部必然相等。同时这也保护了后面 $i = n-3$ 的起点不会取到负数。

第二步，令 $minSuf = nums[n-1]$。 为什么初值是最后一个元素：循环从 $i = n-3$ 开始，此时它对应的后缀是 $[n-1, n-1]$，最小值就是 $nums[n-1]$。初值取别的（比如取一个大常数）会让第一轮的判断失去意义。

第三步，令 $i$ 从 $n-3$ 递减到 0。 为什么从右往左：后缀最小值必须先看右边才能得到，方向反了就无法在常数时间内维护。为什么起点是 $n-3$ 而不是 $n-1$ 或 $n-2$：$i = n-2$ 时 $i+2 = n$ 已越界，$i = n-1$ 更不必说，这两个位置不存在跨度 2 的搭档。

第四步，先执行 $minSuf \leftarrow \min(minSuf,\ nums[i+2])$。 为什么必须先更新：从上一轮到本轮，后缀的左端从 $i+3$ 扩展到了 $i+2$，新进来的元素就是 $nums[i+2]$。不先合并它，不变量在本轮比较时就是错的，会漏掉 $nums[i] > nums[i+2]$ 这类最短跨度的反例。

第五步，若 $nums[i] > minSuf$，立即返回假。 为什么可以立刻返回：只要找到一个非局部的全局倒置，全局数就严格大于局部数，结论已定，无需继续。为什么比较用严格大于：排列中元素互不相同，相等不可能发生；写成 $\ge$ 在本题不会出错，但语义上应该忠实于倒置的定义。

第六步，循环正常结束返回真。

以 nums = [2, 0, 1, 3] 走一遍（$n = 4$）。先手算一下答案：全局倒置是 $(0,1)$ 对应 $2 > 0$、$(0,2)$ 对应 $2 > 1$，共 2 个；局部倒置只有 $(0,1)$，共 1 个。两者不等，期望返回假。

初始化：$minSuf = nums[3] = 3$，含义是后缀 $[3, 3]$ 的最小值。

$i = 1$：先更新 $minSuf \leftarrow \min(3,\ nums[3]) = \min(3, 3) = 3$，此时它代表后缀 $[3, 3]$ 的最小值，与 $i = 1$ 需要的「从下标 3 开始」正好吻合。再比较 $nums[1] = 0 > 3$？不成立，继续。含义是：下标 1 上的元素 0 比它后面（跨度至少 2）的所有元素都小，不构成非局部倒置。

$i = 0$：先更新 $minSuf \leftarrow \min(3,\ nums[2]) = \min(3, 1) = 1$，此时它代表后缀 $[2, 3]$ 的最小值，正是 $i = 0$ 需要的「从下标 2 开始」。再比较 $nums[0] = 2 > 1$？成立，返回假。

返回假，与手算一致。找到的反例正是下标对 $(0, 2)$：$2 > 1$ 且跨度为 2。注意这一步如果把更新与比较的顺序写反，$minSuf$ 在比较时还是 3，$2 > 3$ 不成立，会错误地返回真——这一个用例就足以卡死顺序写反的实现。

再看一个应当返回真的例子 nums = [0, 2, 1, 3]。手算：全局倒置只有 $(1,2)$ 对应 $2 > 1$，局部倒置也只有 $(1,2)$，两者都是 1，相等。

初始化 $minSuf = nums[3] = 3$。$i = 1$：更新 $minSuf = \min(3, nums[3]) = 3$，比较 $nums[1] = 2 > 3$？否。$i = 0$：更新 $minSuf = \min(3, nums[2]) = 1$，比较 $nums[0] = 0 > 1$？否。循环结束返回真。这里的关键是元素 2 只与紧邻的 1 构成倒置，跨度为 1，属于局部倒置，被判定逻辑正确放行。

代码实现

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(n \log n)$ 和暴力两两枚举的 $O(n^2)$，这里的线性来自于「把计数问题降级成存在性判定」。

空间复杂度：$O(1)$。只用了 $minSuf$ 一个标量。特别注意我们没有真的建出一个后缀最小值数组——那样是 $O(n)$ 空间；因为扫描方向与后缀的扩展方向一致，一个滚动变量就够了。

关键点总结

子集关系可以把计数题降级成判定题。局部倒置是全局倒置的子集，所以「相等」等价于「差集为空」。凡是要比较两个计数且其中一个包含另一个，都应该先问：能不能只判断差集是否为空？这一步往往能把复杂度从 $O(n \log n)$ 直接压到 $O(n)$。

「对每个 $i$，是否存在更靠后的更小元素」用后缀极值一次比较解决。把内层循环替换成一个预先维护好的极值，是消除嵌套遍历的通用手法。判断标准是：内层循环求的是否为某种可增量维护的聚合量（最小、最大、和、计数）。

滚动维护后缀信息必须从右往左扫。方向由信息的依赖关系决定，不是随意选的。写这类代码前先问一句「我要的这个量依赖哪一侧的数据」，答案就是扫描的起点。

更新与判断的先后顺序要对齐不变量的定义。本题必须先把 $nums[i+2]$ 合并进 $minSuf$ 再比较，因为不变量声明的是「从 $i+2$ 开始的后缀」。写完循环后逐行核对「此刻这个变量真的等于我声明的那个东西吗」，是最有效的自查方式。

通用判据优于依赖特殊结构的技巧。$ nums[i] - i \le 1$ 更短，但它依赖输入是 $0$ 到 $n-1$ 的排列；后缀最小值判定只用到倒置的定义，换成任意数组、换成「跨度至少为 3」的变体都能改。面试中给出通用解法再补充技巧解法，比只会技巧解法更有说服力。

面试视角：这题的分水岭在于你能否说出「局部倒置是全局倒置的子集」。说出来之后，题目就从「怎么高效数逆序对」变成了「怎么判断有没有跨度 ≥ 2 的逆序对」，难度断崖式下降。面试官常见的追问有两个：一是「$ nums[i] - i \le 1$ 为什么成立」，要能给出「元素偏离排序位置超过 1 就必然造成远距离倒置」的论证；二是「如果要求真的输出两个计数呢」，此时应答归并排序或树状数组求逆序对，并说明那才是 $O(n \log n)$ 的场景。主动指出「先更新后比较的顺序不能反」通常也会被认可，因为这说明你在心里跑过循环。

易错点总结

错误写法：把更新 $minSuf$ 放在比较之后。以 nums = [2, 0, 1, 3] 为例，$i = 0$ 时 $minSuf$ 还停留在 3（没合并 $nums[2] = 1$），比较 $2 > 3$ 不成立而放行，最终返回真，正确答案是假。这是本题第一大错误，且只有当反例恰好出现在跨度为 2 的那一对时才会暴露。

错误写法：循环起点写成 i = n - 2。以 nums = [0, 1, 2] 为例，$i = 1$ 时访问 $nums[3]$ 越界，Java 抛数组越界异常，Go 直接 panic。第一个存在 $i+2$ 的下标是 $n-3$。

错误写法：$minSuf$ 初值取 nums[n-3] 之类与后缀无关的值。以 nums = [0, 2, 1, 3] 为例，初值若取 $nums[1] = 2$，$i = 1$ 时比较 $nums[1] = 2 > \min(2, 3) = 2$ 不成立、$i = 0$ 时 $minSuf = \min(2, 1) = 1$、$0 > 1$ 不成立，碰巧返回真；但换成 nums = [0, 3, 1, 2]，初值取 $nums[1] = 3$ 会让 $minSuf$ 一开始就被污染成一个本不属于后缀的值，判定结果不再可信。初值必须严格等于后缀 $[n-1, n-1]$ 的最小值，也就是 $nums[n-1]$。

错误写法：更新时用 nums[i+1] 而不是 nums[i+2]。以 nums = [0, 2, 1, 3] 为例，$i = 0$ 时 $minSuf$ 会把 $nums[1] = 2$ 也算进去（实际应从下标 2 起算），虽然本例结果仍为真，但换成 nums = [1, 0, 2]：正确流程 $minSuf = nums[2] = 2$，$1 > 2$ 不成立返回真；用 $nums[i+1]$ 会把 $nums[1] = 0$ 纳入，$1 > 0$ 成立返回假，而正确答案是真（唯一的倒置 $(0,1)$ 是局部的）。把局部倒置误判成非局部倒置，是这个偏移错误的典型后果。

错误写法：从左往右扫描并维护「前缀最小值」。以 nums = [2, 0, 1, 3] 为例，前缀信息回答不了「后面有没有更小的元素」这个问题，无论怎么比较都得不到正确结论。判定条件里的量词是「存在更靠后的 $j$」，只能用后缀。

错误写法：漏掉 n < 3 的提前返回。以 nums = [1, 0] 为例，$i$ 从 $n - 3 = -1$ 开始，循环条件 $i \ge 0$ 直接不成立所以碰巧不崩；但 $minSuf = nums[n-1] = nums[1]$ 这一行在 $n = 1$ 时读的是 $nums[0]$ 也还算安全——真正的风险在于把初值行写成 nums[n-2]，$n = 1$ 时下标为 $-1$ 直接越界。显式的短路分支让边界意图一目了然。

错误写法：老老实实数出两个计数再比较。以 $n = 10^5$ 的输入为例，两两枚举全局倒置是 $10^{10}$ 次比较，必然超时。即使用归并排序降到 $O(n \log n)$，也比线性判定慢且代码长得多，面试中还要额外解释归并计数的正确性。

错误写法：把「局部倒置」理解成「任意小跨度的倒置」。以 nums = [2, 0, 1, 3] 为例，若把跨度 2 也算作局部，两个计数都变成 2，返回真，而正确答案是假。局部倒置的定义严格限定 $j = i + 1$。

**错误写法：用 $ nums[i] - i \le 1$ 但写成 $ nums[i] - i < 1$**。以 nums = [1, 0] 为例，$ 1 - 0 = 1$ 不小于 1，被判为假，而正确答案是真。这个技巧判据允许元素偏离一格，边界必须取等。

错误写法：找到反例后不返回，而是置标志继续扫完。以 nums = [n-1, n-2, \dots, 0] 这类完全逆序的输入为例，第一轮就能确定答案，却要白扫 $10^5$ 次；逻辑虽对，但放弃了提前退出的收益，面试中会被追问为什么不短路。

错误写法：把 minSuf 声明在循环内部、每轮重新初始化。以 nums = [2, 0, 3, 1] 为例，$i = 0$ 时 $minSuf$ 只等于 $nums[2] = 3$ 而不是后缀 $[2, 3]$ 的最小值 1，比较 $2 > 3$ 不成立而放行，返回真；实际下标对 $(0, 3)$ 满足 $2 > 1$ 且跨度为 3，正确答案是假。滚动变量必须活在循环之外，才能累积整段后缀的信息。

相似题目

题目	难度	考察点
剑指 Offer 51. 数组中的逆序对	困难	真的要数出全局倒置个数，需归并排序或树状数组，是本题「不必计数」的反面
315. 计算右侧小于当前元素的个数	困难	逐位置统计右侧更小元素数量，同样关注右侧信息但要求精确计数而非存在性
493. 翻转对	困难	判据从 $a > b$ 变成 $a > 2b$，归并时的双指针统计要单独走一遍
665. 非递减数列	中等	允许修改一个元素使数组非递减，同样是「最多容忍一处异常」的线性判定
581. 最短无序连续子数组	中等	用前缀最大与后缀最小定位必须重排的区间边界，是后缀极值技巧的直接延伸
629. K 个逆序对数组	困难	反过来构造恰有 $k$ 个逆序对的排列个数，需前缀和优化的 DP
41. 缺失的第一个正数	困难	同样利用「元素应落在特定位置」的排列性质，但走的是原地交换归位路线