LeetCode 629. K 个逆序对数组

2025-11-20 HGNULB 约 12 分钟

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

分类

题目描述

✅ 629. K 个逆序对数组

题意分析

给定 $n$ 和 $k$，统计由 1 到 $n$ 这 $n$ 个互不相同的数组成的全排列中，恰好含有 $k$ 个逆序对的排列有多少个，答案对 $10^9 + 7$ 取模。逆序对指下标 $i < j$ 但值 $a_i > a_j$ 的数对。

要什么：是方案计数，不是构造某一个排列，也不是给定排列去数逆序对。方向恰好和常见的「归并排序求逆序对」相反——那类题是「排列 → 逆序对数」，这题是「逆序对数 → 排列个数」。识别出这个方向，才不会一上来就往树状数组上想。

约束透露的信号：$n$ 与 $k$ 都在 $10^3$ 量级。这意味着 $O(n \cdot k)$ 约 $10^6$ 完全可行，$O(n \cdot k^2)$ 约 $10^9$ 会超时，而排列总数 $n!$ 级别的枚举更是天方夜谭。「两个维度都是千级、答案要取模」这三条组合起来，几乎是在直接点名：二维计数 DP，且内层的求和必须被优化成常数。

另一个信号是取模。取模说明答案会大到爆 long，所以中间一定要边算边取模；而一旦后面用到「窗口求和」这类带减法的技巧，取模后的值可能变成负数，必须显式归一化。

边界：$k = 0$ 时只有升序排列一种，答案恒为 1；$k$ 超过 $n$ 个数能产生的逆序对上限 $n(n-1)/2$ 时答案为 0，代码应当自然算出 0 而不是越界；$n = 1$ 时只有一个排列，逆序对数为 0。

解法：滚动数组 + 前缀窗口优化

核心思路

先看暴力：枚举 $1..n$ 的全部 $n!$ 个排列，对每个排列数一遍逆序对。$n = 1000$ 时这个数字大到没有意义。瓶颈在于排列之间存在海量的重复子结构——两个排列只要「前 $i$ 个元素的相对大小关系」相同，后续的可能性就完全一样，逐个枚举是在反复重算同一件事。

于是想到按元素规模递推。关键观察是：把最大的那个数 $i$ 插入到 $1..i-1$ 的某个排列里，它贡献的新逆序对个数只取决于它右边有几个元素。因为 $i$ 比其余所有数都大，它与右边每一个元素都构成逆序对，与左边任何元素都不构成。若把 $i$ 插到「右边恰好有 $x$ 个元素」的位置，就恰好新增 $x$ 个逆序对，且 $x$ 可以取遍 $0, 1, \dots, i-1$，每个取值对应唯一一个插入位置。更妙的是，插入 $i$ 完全不影响原有 $i-1$ 个元素之间的相对顺序，所以原有的逆序对数原封不动地保留。

由此写出状态定义与转移：

状态定义：$dp[i][j]$ 表示用 $1$ 到 $i$ 这 $i$ 个数构成的排列中，逆序对恰好为 $j$ 个的排列数目。
\[dp[i][j] = \sum_{x=0}^{\min(j,\ i-1)} dp[i-1][j-x]\]
初值 $dp[0][0] = 1$（空排列有且只有一个，逆序对数为 0），$dp[0][j] = 0\ (j > 0)$。答案是 $dp[n][k]$。

直接照这个式子写是三重循环，$O(n k^2)$，$10^9$ 级别会超时。看这个求和式：它是 $dp[i-1]$ 这一行上一段长度固定为 $i$、右端点为 $j$ 的连续区间的和（当 $j < i$ 时左端被 0 截断）。$j$ 每增加 1，区间整体右移一格：右边进来 $dp[i-1][j]$，左边出去 $dp[i-1][j-i]$。这正是滑动窗口，于是内层求和可以 $O(1)$ 增量维护：
\[\text{window}_j = \text{window}_{j-1} + dp[i-1][j] - dp[i-1][j-i] \quad (j \ge i \text{ 时才减})\]
这就把总复杂度压到 $O(n k)$。

最后一层优化是空间：转移只依赖上一行，用 prev 与 cur 两个长度 $k+1$ 的数组滚动即可，空间从 $O(nk)$ 降到 $O(k)$。

还有一个实现上的坑必须提前定好：窗口里有减法，而 prev 中存的是已经取模后的值，所以 window 减完可能为负。必须在每次更新后先 %= MOD，若结果为负再加回一个 MOD，保证 window 始终落在 $[0, MOD)$ 内。这一步是本题写崩率最高的地方。

解题步骤

开两个 long[k + 1] 数组 prev 与 cur，令 prev[0] = 1。为什么用 long 而不是 int：窗口累加与减法的中间值会短暂超出 int 范围；为什么 prev[0] = 1：它代表 $dp[0][0]$，即空排列这唯一一种「零个数、零个逆序对」的方案，整个递推的所有计数都从这个 1 生长出来。

外层 i 从 1 递增到 n，每轮把 window 重置为 0。为什么必须重置：window 表示的是在当前行 $i$ 下的滑动窗口和，窗口长度是 $i$，行与行之间语义不同，跨行沿用会把上一行的残留值混进来。

内层 j 从 0 到 k，先执行 window += prev[j]。为什么先加：窗口的右端点就是 $j$，新的 $j$ 一进来对应的 $dp[i-1][j]$（即 $x = 0$，把 $i$ 插到最右端不产生新逆序对的情况）必须先纳入。

当 j >= i 时执行 window -= prev[j - i]。为什么是 j - i 而不是 j - i + 1：窗口要保留的是 $dp[i-1][j-i+1]$ 到 $dp[i-1][j]$ 共 $i$ 项，刚好对应 $x = 0..i-1$；再往左的 $dp[i-1][j-i]$ 对应 $x = i$，超出了「$i$ 最多只能有 $i-1$ 个元素在其右侧」的物理上限，必须剔除。为什么只在 j >= i 时减：$j < i$ 时窗口左端已经被数组左边界截断，没有需要移出的元素。

window %= MOD 后若为负再 window += MOD，然后写入 cur[j]。为什么必须归一化：prev[j - i] 是取模后的代表元，减法可能得到负数；负数直接存进 cur 会污染下一行的所有窗口和，并让最终答案变成负值。

一行算完后交换 prev 与 cur，并把新的 cur 清零。为什么交换而不是拷贝：交换是 $O(1)$ 的引用互换，拷贝是 $O(k)$，在 $n$ 轮下白白多花 $O(nk)$。

返回 (int) prev[k]。为什么是 prev 不是 cur：最后一轮结束时刚做过交换，$dp[n]$ 这一行躺在 prev 里。

以 具体用例 n = 3, k = 1 走一遍，预期答案是 2（[1,3,2] 与 [2,1,3] 这两个排列各有一个逆序对）。数组长度为 k + 1 = 2。

初始：prev = [1, 0]，即 $dp[0][0] = 1$、$dp[0][1] = 0$。

$i = 1$（窗口长度 1）：window = 0。
j = 0：window += prev[0] = 1 → window = 1；j >= 1 不成立，不减；cur[0] = 1。含义是只用 {1} 排成 0 个逆序对，有 1 种。
j = 1：window += prev[1] = 0 → 仍是 1；j >= 1 成立，window -= prev[0] = 1 → window = 0；cur[1] = 0。含义是只用 {1} 不可能凑出 1 个逆序对。这一减正是「$x$ 最多取 $i - 1 = 0$」的体现。
交换后 prev = [1, 0]。

$i = 2$（窗口长度 2）：window = 0。
j = 0：window += prev[0] = 1 → 1；j >= 2 不成立；cur[0] = 1。即 [1,2]，唯一的零逆序对排列。
j = 1：window += prev[1] = 0 → 仍是 1；j >= 2 不成立，不减，窗口保留了 $dp[1][1] + dp[1][0] = 0 + 1 = 1$；cur[1] = 1。即 [2,1]，唯一的一逆序对排列。这里体现了把 2 插到左端（$x = 1$）新增一个逆序对。
交换后 prev = [1, 1]。

$i = 3$（窗口长度 3）：window = 0。
j = 0：window += prev[0] = 1 → 1；cur[0] = 1。即 [1,2,3]。
j = 1：window += prev[1] = 1 → window = 2；j >= 3 不成立，不减；cur[1] = 2。这个 2 恰好由两部分构成：把 3 插到最右端（$x = 0$）作用在 $dp[2][1] = 1$ 上，得到 [2,1,3]；把 3 插到中间（$x = 1$）作用在 $dp[2][0] = 1$ 上，得到 [1,3,2]。
交换后 prev = [1, 2]。

循环结束，返回 prev[1] = 2，与预期一致。

代码实现

class Solution {
    // dp[i][j] 到 dp[i-1][j-x] 的转移可由滑动窗口优化成 O(1) 更新。
    private static final int MOD = 1_000_000_007;

    public int kInversePairs(int n, int k) {
        long[] prev = new long[k + 1];
        long[] cur = new long[k + 1];
        prev[0] = 1;

        for (int i = 1; i <= n; i++) {
            long window = 0;
            for (int j = 0; j <= k; j++) {
                window += prev[j];
                if (j >= i) {
                    window -= prev[j - i];
                }
                window %= MOD;
                if (window < 0) {
                    window += MOD;
                }
                cur[j] = window;
            }
            long[] previous = prev;
            prev = cur;
            cur = previous;
            for (int j = 0; j <= k; j++) {
                cur[j] = 0;
            }
        }
        return (int) prev[k];
    }
}

const mod629 = 1_000_000_007

func kInversePairs(n int, k int) int {
    // dp[i][j] 到 dp[i-1][j-x] 的转移可由滑动窗口优化成 O(1) 更新。
    prev := make([]int64, k+1)
    cur := make([]int64, k+1)
    prev[0] = 1

    for i := 1; i <= n; i++ {
        var window int64
        for j := 0; j <= k; j++ {
            window += prev[j]
            if j >= i {
                window -= prev[j-i]
            }
            window %= mod629
            if window < 0 {
                window += mod629
            }
            cur[j] = window
        }
        prev, cur = cur, prev
        for j := 0; j <= k; j++ {
            cur[j] = 0
        }
    }
    return int(prev[k])
}

复杂度分析

时间复杂度：$O(n \cdot k)$。凭什么：外层 $n$ 轮，内层 $k + 1$ 个状态，每个状态只做一次加、至多一次减、一次取模，全是常数操作；原始转移里那个长度可达 $i$ 的求和被滑动窗口摊成了 $O(1)$，否则会是 $O(n k^2)$。行末的清零同样是 $O(k)$，不改变量级。

空间复杂度：$O(k)$。凭什么：转移只依赖紧邻的上一行 $dp[i-1]$，所以完整的 $O(nk)$ 表格被压成 prev 与 cur 两个长度 $k+1$ 的数组来回滚动；代价是无法回溯出具体是哪些排列，但本题只要计数，不需要方案。

关键点总结

计数 DP 的状态设计应当沿着「最后一个决策」展开。这里的决策是「把最大的数 $i$ 插到哪个位置」，之所以选最大的数，是因为它与其余元素的大小关系完全确定，新增逆序对的数量能被单一变量 $x$ 精确刻画。若改成插入最小的数或任意位置的数，转移会立刻纠缠不清。

转移式一旦呈现「上一行某段连续区间求和」的形态，立刻考虑前缀和或滑动窗口。这是把 DP 从 $O(n k^2)$ 降到 $O(n k)$ 的通用手法，同类的还有背包的单调队列优化、区间和的差分。

窗口长度 $i$ 的物理含义要能一句话说清：$i$ 最多只有 $i-1$ 个元素在它右边，所以 $x \in [0, i-1]$，共 $i$ 种选择。记不住 j - i 还是 j - i + 1 时，回到这句话推一遍比死记靠谱。

模意义下做减法必须归一化。取模后的值是同余类的代表元，减法会跌破 0；%= MOD 之后紧跟一次 if (< 0) += MOD 应当成为肌肉记忆，凡是「前缀和相减」「容斥」「窗口滑动」的模运算场景一律适用。

滚动数组要用引用交换而非逐元素拷贝，并想清楚最后一次交换之后答案落在哪个数组里——这是滚动写法最常见的低级错误来源。

面试视角：这题被问到时，面试官关心的不是你能否背出代码，而是能否独立走完「$n!$ 暴力 → 按最大元素插入的 $O(nk^2)$ DP → 发现区间求和 → 滑动窗口 $O(nk)$ → 滚动数组 $O(k)$」这条完整的优化链。建议先在白板上把 $dp[i][j]$ 的定义和转移式写清楚再动手，并主动指出「窗口相减在模意义下要防负数」——这句话往往比代码本身更能说明你真写过取模计数题。

易错点总结

错误写法：window -= prev[j - i + 1]（窗口左端点算错一位） → 用例 n = 3, k = 1，$i = 2$ 时在 j = 1 处误减掉 prev[0] = 1，cur[1] 变成 0，最终答案错成 1（正确是 2）。窗口要覆盖 $x = 0..i-1$ 共 $i$ 项，被移出的是 $dp[i-1][j-i]$。

错误写法：window %= MOD 后不做负数归一化 → 用例 n = 1000, k = 1000，某轮 prev[j] = 3 而 prev[j - i] = 10^9 + 5，window 变成一个负数并原样写入 cur[j]，负值随后被后续行反复累加放大，最终返回负数，判题直接 WA。

错误写法：把 window 声明成 int → 用例 n = 1000, k = 1000，window 在取模前会短暂达到约 $2 \times 10^9$，超过 int 上限 $2147483647$ 而溢出为负，后续归一化把错误值「洗白」成一个合法但错误的非负数，错误极难定位。

错误写法：外层每轮忘记 window = 0 → 用例 n = 3, k = 1，$i = 2$ 起的窗口带着 $i = 1$ 行残留的和开始累加，cur[0] 立刻算成 2，答案整体偏大。

错误写法：prev[0] = 1 写成 prev[0] = 0 或整体不初始化 → 任意用例下所有 $dp$ 值恒为 0，返回 0。递推的全部计数都从「空排列有 1 种」这个种子生长出来，种子为 0 则整棵树为 0。

错误写法：最后返回 cur[k] → 用例 n = 3, k = 1，最后一轮交换后 cur 已被清零，返回 0 而非 2。滚动数组务必确认交换之后哪个数组持有最新一行。

错误写法：if (j >= i) 写成 if (j > i) → 用例 n = 4, k = 3，$i = 2$ 时 j = 2 处该移出的 prev[0] 没被移出，窗口长度变成 3 而不是 2，等于允许把元素 2 插到「右边有 2 个元素」的不存在位置，方案数被高估。

错误写法：为了省事把内层写成三重循环 for (int x = 0; x <= Math.min(j, i - 1); x++) → 用例 n = 1000, k = 1000，运算量约 $5 \times 10^8$ 次带取模的加法，稳定超时；逻辑虽对但没有完成本题真正考察的优化。

错误写法：先判 if (k > n * (n - 1) / 2) return 0 但用 int 算这个上限 → 用例 n = 1000 时 n * (n - 1) / 2 = 499500 尚且安全，但把这个特判照搬到 $n$ 更大的变形题时 int 会溢出；本题主逻辑本就能自然算出 0，这个特判纯属多余风险。

错误写法：把 cur 的清零省略，同时又在某些分支下 continue 跳过对 cur[j] 的赋值 → 任意用例下被跳过的位置会残留两行之前的旧值，产生完全无规律的错误；要么保证每个 cur[j] 都被无条件覆盖，要么老实清零，二者必居其一。

相似题目

题目	难度	考察点
剑指 Offer 51. 数组中的逆序对	困难	方向相反，给定数组求逆序对数量，靠归并排序在合并时统计跨段贡献
315. 计算右侧小于当前元素的个数	困难	要求逐个下标的逆序对贡献而非总数，需要树状数组或归并时记录原始下标
493. 翻转对	困难	判定条件变成 $a_i > 2 a_j$，归并时必须用独立的双指针扫一遍才能统计
920. 播放列表的数量	困难	同为「逐个加入新元素」的排列计数 DP，但转移靠组合数拆分新歌与旧歌两类情形
1420. 生成数组	困难	三维计数 DP，同样发现内层是区间求和后用前缀和降维，是本题优化手法的直接迁移
96. 不同的二叉搜索树	中等	也是结构计数，但转移是左右子树规模的卷积，无法用滑动窗口，只能老实做卡特兰递推