LeetCode 629. K 个逆序对数组

约 5 分钟
文章信息 7 个分类 1 个标签
分类
LeetCode CodeTop 困难 未解决 2-5 字节 拼多多
标签
动态规划

题目描述

✅ 629. K 个逆序对数组

image-20260928224354936

题意分析

用 $1$ 到 $n$ 的每个整数各一次组成排列，统计其中恰好有 $k$ 个逆序对的排列数量。逆序对是位置靠前、数值却更大的一对元素，答案对 $10^9+7$ 取模。

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

核心思路

[!blue]

定义 dp[i][j] 为用 $1$ 到 $i$ 组成、恰好有 $j$ 个逆序对的排列数量。把最大元素 $i$ 插入一个由前 $i-1$ 个数组成的排列时，原有元素的相对顺序不变；$i$ 与右侧每个元素都形成逆序对，因此新增数量 $t$ 可以是 $0$ 到 $i-1$。

每个插入位置对应唯一的 $t$。反过来，从一个最终排列中删除 $i$，也会唯一确定原排列和新增逆序对数，所以不会重复或遗漏计数。转移为 $dp[i][j]=\sum_{t=0}^{\min(j,i-1)}dp[i-1][j-t]$。

直接对每个状态求和会反复累加重叠区间。用 prev 保存上一行时，dp[i][j] 就是下标从 max(0, j-i+1) 到 j 的连续区间和。让 j 从小到大增加，每次加入右端 prev[j]；当 j >= i 时，再移除刚越过左边界的 prev[j-i]，便能用一次加减维护新窗口。

空排列只有一种且没有逆序对，所以初始化 prev[0] = 1，其他位置为 $0$。每行重新把窗口和设为 $0$，算完后交换前后两行；所有加减都按模数计算，取余为负时再加一次模数，恢复非负结果。

解题步骤

  1. 创建长度为 k + 1 的 prev、cur，令 prev[0] = 1。
  2. 从 $i=1$ 到 $n$ 枚举排列规模，每行令 window = 0。
  3. 从 $j=0$ 到 $k$ 枚举逆序对数，加入 prev[j]，必要时减去 prev[j-i]，取模后写入 cur[j]。
  4. 算完整行后交换数组，让 prev 始终指向最新结果，最后返回 prev[k]。

$k=0$ 时，每一行的零逆序对方案数都是 $1$，对应升序排列。若 $k>n(n-1)/2$，超过排列最多能有的逆序对数，转移得到的相应状态自然为 $0$。

代码实现

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];

                // 移出对应新增 i 个逆序对的项，只允许新增零到 i 减一
                if (j >= i) {
                    window -= prev[j - i];
                }

                window %= MOD;

                // 模意义下的减法可能为负，恢复到非负代表值
                if (window < 0) {
                    window += MOD;
                }

                cur[j] = window;
            }

            long[] previous = prev;

            // 最新一行交换到 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]
            // 移出对应新增 i 个逆序对的项，只允许新增零到 i 减一
            if j >= i {
                window -= prev[j-i]
            }
            window %= mod629
            // 模意义下的减法可能为负，恢复到非负代表值
            if window < 0 {
                window += mod629
            }
            cur[j] = window
        }
        // 最新一行交换到 prev，下一轮继续读取它
        prev, cur = cur, prev
        for j := 0; j <= k; j++ {
            cur[j] = 0
        }
    }
    return int(prev[k])
}

复杂度分析

  • 时间复杂度：$O(n(k+1))$，每行 k+1 个状态。
  • 空间复杂度：$O(k+1)$，只保留相邻两行。

关键点总结

[!green]

  • 窗口最多 i 项，对应新增零到 i−1 个逆序对。
  • 模运算中的减法可能为负，需要恢复到非负代表值。

易错点总结

[!yellow]

  • 移除 j-i+1 而不是 j-i，会改变允许的新增逆序数。
  • 每行不重置窗口，会混入上一行残留。
  • 交换后返回旧缓冲，会取错最后一行。

相似题目

题目 难度 关联与区别
903. DI 序列的有效排列 困难 同样按排列的名次关系做计数DP，可用前缀和加速一整段前驱状态的求和。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/leetcode-629
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！