Hard

题目描述

给你一个整数 n 和一个二维数组 requirements，其中 requirements[i] = [endi, cnti] 表示每个要求的结束索引和逆序对数量。

对于整数数组 nums，如果满足以下条件，则称一对索引 (i, j) 为逆序对：

  • i < j 且 nums[i] > nums[j]

返回 [0, 1, 2, ..., n - 1] 的排列 perm 的数量，使得对于所有 requirements[i]，perm[0..endi] 恰好有 cnti 个逆序对。

由于答案可能很大，请返回答案对 10^9 + 7 取模的结果。

示例 1：

输入：n = 3, requirements = [[2,2],[0,0]]

输出：2

解释：

两个排列是：

  • [2, 0, 1]

    • 前缀 [2, 0, 1] 有逆序对 (0, 1) 和 (0, 2)
    • 前缀 [2] 有 0 个逆序对

  • [1, 2, 0]

    • 前缀 [1, 2, 0] 有逆序对 (0, 2) 和 (1, 2)
    • 前缀 [1] 有 0 个逆序对

示例 2：

输入：n = 3, requirements = [[2,2],[1,1],[0,0]]

输出：1

示例 3：

输入：n = 2, requirements = [[0,0],[1,0]]

输出：1

约束条件：

  • 2 <= n <= 300
  • 1 <= requirements.length <= n
  • requirements[i] = [endi, cnti]
  • 0 <= endi <= n - 1
  • 0 <= cnti <= 400
  • 输入保证至少有一个 i 使得 endi == n - 1
  • 输入保证所有 endi 都是唯一的

解题思路

这是一道动态规划问题，核心思想是逐步构建排列，同时记录逆序对的数量。

思路分析

首先理解题意：我们需要找到 [0,1,2,…,n-1] 的所有排列，使得在指定位置的前缀子数组恰好包含指定数量的逆序对。

动态规划状态定义：

  • dp[i][j] 表示长度为 i 的数组中恰好有 j 个逆序对的排列数量

状态转移： 当我们在长度为 i-1 的数组末尾插入一个新元素时，这个元素可以是 0 到 i-1 中的任意一个。如果插入的元素在排序后的位置是第 k 个（从右数），那么会新增 k 个逆序对。

因此：dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + ... + dp[i-1][max(0, j-i+1)]

约束处理： 对于每个 requirement [end_i, cnt_i]，我们必须确保 dp[end_i+1][cnt_i] 是唯一可能的状态，其他状态都设为 0。

优化： 使用前缀和优化状态转移，避免重复计算。

这个问题的关键在于正确处理约束条件，确保在指定位置只有指定数量的逆序对是合法的。

代码实现

class Solution {
public:
    int numberOfPermutations(int n, vector<vector<int>>& requirements) {
        const int MOD = 1e9 + 7;
        
        // 记录每个位置的要求
        map<int, int> req_map;
        for (auto& req : requirements) {
            req_map[req[0]] = req[1];
        }
        
        // dp[i][j] = 长度为i的数组中有j个逆序对的方案数
        vector<vector<int>> dp(n + 1, vector<int>(401, 0));
        dp[0][0] = 1;
        
        for (int i = 1; i <= n; i++) {
            vector<long long> prefix(401, 0);
            
            // 计算前缀和
            for (int j = 0; j <= 400; j++) {
                prefix[j] = (j > 0 ? prefix[j-1] : 0) + dp[i-1][j];
                prefix[j] %= MOD;
            }
            
            for (int j = 0; j <= 400; j++) {
                // 状态转移：新插入元素可能产生0到min(i-1, j)个逆序对
                int max_inv = min(i-1, j);
                long long sum = prefix[j] - (j > max_inv ? prefix[j - max_inv - 1] : 0);
                dp[i][j] = (sum % MOD + MOD) % MOD;
            }
            
            // 应用约束条件
            if (req_map.count(i-1)) {
                int required = req_map[i-1];
                for (int j = 0; j <= 400; j++) {
                    if (j != required) {
                        dp[i][j] = 0;
                    }
                }
            }
        }
        
        return dp[n][req_map[n-1]];
    }
};

class Solution:
    def numberOfPermutations(self, n: int, requirements: List[List[int]]) -> int:
        MOD = 10**9 + 7
        
        # 记录每个位置的要求
        req_map = {end: cnt for end, cnt in requirements}
        
        # dp[i][j] = 长度为i的数组中有j个逆序对的方案数
        dp = [[0] * 401 for _ in range(n + 1)]
        dp[0][0] = 1
        
        for i in range(1, n + 1):
            # 计算前缀和
            prefix = [0] * 401
            for j in range(401):
                prefix[j] = (prefix[j-1] if j > 0 else 0) + dp[i-1][j]
                prefix[j] %= MOD
            
            for j in range(401):
                # 状态转移：新插入元素可能产生0到min(i-1, j)个逆序对
                max_inv = min(i-1, j)
                total = prefix[j] - (prefix[j - max_inv - 1] if j > max_inv else 0)
                dp[i][j] = total % MOD
            
            # 应用约束条件
            if (i-1) in req_map:
                required = req_map[i-1]
                for j in range(401):
                    if j != required:
                        dp[i][j] = 0
        
        return dp[n][req_map[n-1]]

public class Solution {
    public int NumberOfPermutations(int n, int[][] requirements) {
        const int MOD = 1000000007;
        
        // 记录每个位置的要求
        var reqMap = new Dictionary<int, int>();
        foreach (var req in requirements) {
            reqMap[req[0]] = req[1];
        }
        
        // dp[i][j] = 长度为i的数组中有j个逆序对的方案数
        var dp = new int[n + 1][];
        for (int i = 0; i <= n; i++) {
            dp[i] = new int[401];
        }
        dp[0][0] = 1;
        
        for (int i = 1; i <= n; i++) {
            // 计算前缀和
            var prefix = new long[401];
            for (int j = 0; j < 401; j++) {
                prefix[j] = (j > 0 ? prefix[j-1] : 0) + dp[i-1][j];
                prefix[j] %= MOD;
            }
            
            for (int j = 0; j < 401; j++) {
                // 状态转移：新插入元素可能产生0到min(i-1, j)个逆序对
                int maxInv = Math.Min(i-1, j);
                long sum = prefix[j] - (j > maxInv ? prefix[j - maxInv - 1] : 0);
                dp[i][j] = (int)((sum % MOD + MOD) % MOD);
            }
            
            // 应用约束条件
            if (reqMap.ContainsKey(i-1)) {
                int required = reqMap[i-1];
                for (int j = 0; j < 401; j++) {
                    if (j != required) {
                        dp[i][j] = 0;
                    }
                }
            }
        }
        
        return dp[n][reqMap[n-1]];
    }
}

var numberOfPermutations = function(n, requirements) {
    const MOD = 1e9 + 7;
    
    // 记录每个位置的要求
    const reqMap = new Map();
    for (const [end, cnt] of requirements) {
        reqMap.set(end, cnt);
    }
    
    // dp[i][j] = 长度为i的数组中有j个逆序对的方案数
    const dp = Array(n + 1).fill(null).map(() => Array(401).fill(0));
    dp[0][0] = 1;
    
    for (let i = 1; i <= n; i++) {
        // 计算前缀和
        const prefix = Array(401).fill(0);
        for (let j = 0; j < 401; j++) {
            prefix[j] = (j > 0 ? prefix[j-1] : 0) + dp[i-1][j];
            prefix[j] %= MOD;
        }
        
        for (let j = 0; j < 401; j++) {
            // 状态转移：新插入元素可能产生0到min(i-1, j)个逆序对
            const maxInv = Math.min(i-1, j);
            const sum = prefix[j] - (j > maxInv ? prefix[j - maxInv - 1] : 0);
            dp[i][j] = ((sum % MOD) + MOD) % MOD;
        }
        
        // 应用约束条件
        if (reqMap.has(i-1)) {
            const required = reqMap.get(i-1);
            for (let j = 0; j < 401; j++) {
                if (j !== required) {
                    dp[i][j] = 0;
                }
            }
        }
    }
    
    return dp[n][reqMap.get(n-1)];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度时间复杂度空间复杂度
时间复杂度O(n × M)O(n × M)
空间复杂度O(n × M)O(n × M)

其中 M = 401 是逆序对数量的上界。时间复杂度主要来自于双重循环的状态转移，空间复杂度来自于二维DP数组的存储。

相关题目