Hard

题目描述

给你一个长度为 n 的正整数数组 nums。

如果一对非负整数数组 (arr1, arr2) 满足以下条件，我们称之为单调数对：

  • 两个数组的长度都是 n
  • arr1 单调非递减，换句话说，arr1[0] <= arr1[1] <= ... <= arr1[n - 1]
  • arr2 单调非递增，换句话说，arr2[0] >= arr2[1] >= ... >= arr2[n - 1]
  • 对于所有 0 <= i <= n - 1，都有 arr1[i] + arr2[i] == nums[i]

返回单调数对的数目。

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

示例 1：

输入：nums = [2,3,2]
输出：4
解释：
好的数对有：
([0, 1, 1], [2, 2, 1])
([0, 1, 2], [2, 2, 0])
([0, 2, 2], [2, 1, 0])
([1, 2, 2], [1, 1, 0])

示例 2：

输入：nums = [5,5,5,5]
输出：126

提示：

  • 1 <= n == nums.length <= 2000
  • 1 <= nums[i] <= 1000

解题思路

这是一个经典的动态规划问题，关键在于理解约束条件并设计合适的状态转移。

分析约束条件：

  • arr1[i] + arr2[i] = nums[i]，所以 arr2[i] = nums[i] - arr1[i]
  • arr1 非递减：arr1[i] >= arr1[i-1]
  • arr2 非递增：arr2[i] <= arr2[i-1]，即 nums[i] - arr1[i] <= nums[i-1] - arr1[i-1]

化简第三个条件得到：arr1[i] >= arr1[i-1] + nums[i] - nums[i-1]

因此，arr1[i] 的取值范围是： max(arr1[i-1], arr1[i-1] + nums[i] - nums[i-1]) <= arr1[i] <= nums[i]

动态规划思路：

  • 状态定义：dp[i][j] 表示前 i 个位置，第 i 位置 arr1[i] = j 时的方案数
  • 状态转移：对于每个位置 i 和值 j，累加所有满足条件的前一个状态
  • 优化：使用前缀和优化状态转移，将时间复杂度从 O(n²·max_val²) 降到 O(n²·max_val)

边界情况： 第一个位置 arr1[0] 可以取 0 到 nums[0] 的任意值，每种取值都是 1 种方案。

代码实现

class Solution {
public:
    int countOfPairs(vector<int>& nums) {
        const int MOD = 1e9 + 7;
        int n = nums.size();
        int maxVal = *max_element(nums.begin(), nums.end());
        
        // dp[j] 表示当前位置 arr1[i] = j 时的方案数
        vector<long long> dp(maxVal + 1, 0);
        vector<long long> newDp(maxVal + 1, 0);
        
        // 初始化第一个位置
        for (int j = 0; j <= nums[0]; j++) {
            dp[j] = 1;
        }
        
        // 动态规划
        for (int i = 1; i < n; i++) {
            fill(newDp.begin(), newDp.end(), 0);
            vector<long long> prefixSum(maxVal + 1, 0);
            
            // 计算前缀和
            for (int j = 0; j <= maxVal; j++) {
                prefixSum[j] = (j > 0 ? prefixSum[j-1] : 0) + dp[j];
                prefixSum[j] %= MOD;
            }
            
            for (int j = 0; j <= nums[i]; j++) {
                int minPrev = max(0, j - (nums[i] - nums[i-1]));
                int maxPrev = j;
                
                if (minPrev <= maxPrev) {
                    newDp[j] = prefixSum[maxPrev] - (minPrev > 0 ? prefixSum[minPrev-1] : 0);
                    newDp[j] = (newDp[j] % MOD + MOD) % MOD;
                }
            }
            
            dp = newDp;
        }
        
        long long result = 0;
        for (int j = 0; j <= maxVal; j++) {
            result = (result + dp[j]) % MOD;
        }
        
        return result;
    }
};

class Solution:
    def countOfPairs(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        max_val = max(nums)
        
        # dp[j] 表示当前位置 arr1[i] = j 时的方案数
        dp = [0] * (max_val + 1)
        
        # 初始化第一个位置
        for j in range(nums[0] + 1):
            dp[j] = 1
        
        # 动态规划
        for i in range(1, n):
            new_dp = [0] * (max_val + 1)
            
            # 计算前缀和
            prefix_sum = [0] * (max_val + 1)
            for j in range(max_val + 1):
                prefix_sum[j] = (prefix_sum[j-1] if j > 0 else 0) + dp[j]
                prefix_sum[j] %= MOD
            
            for j in range(nums[i] + 1):
                min_prev = max(0, j - (nums[i] - nums[i-1]))
                max_prev = j
                
                if min_prev <= max_prev:
                    new_dp[j] = prefix_sum[max_prev] - (prefix_sum[min_prev-1] if min_prev > 0 else 0)
                    new_dp[j] = (new_dp[j] % MOD + MOD) % MOD
            
            dp = new_dp
        
        return sum(dp) % MOD

public class Solution {
    public int CountOfPairs(int[] nums) {
        const int MOD = 1000000007;
        int n = nums.Length;
        int maxVal = nums.Max();
        
        // dp[j] 表示当前位置 arr1[i] = j 时的方案数
        long[] dp = new long[maxVal + 1];
        
        // 初始化第一个位置
        for (int j = 0; j <= nums[0]; j++) {
            dp[j] = 1;
        }
        
        // 动态规划
        for (int i = 1; i < n; i++) {
            long[] newDp = new long[maxVal + 1];
            long[] prefixSum = new long[maxVal + 1];
            
            // 计算前缀和
            for (int j = 0; j <= maxVal; j++) {
                prefixSum[j] = (j > 0 ? prefixSum[j-1] : 0) + dp[j];
                prefixSum[j] %= MOD;
            }
            
            for (int j = 0; j <= nums[i]; j++) {
                int minPrev = Math.Max(0, j - (nums[i] - nums[i-1]));
                int maxPrev = j;
                
                if (minPrev <= maxPrev) {
                    newDp[j] = prefixSum[maxPrev] - (minPrev > 0 ? prefixSum[minPrev-1] : 0);
                    newDp[j] = (newDp[j] % MOD + MOD) % MOD;
                }
            }
            
            dp = newDp;
        }
        
        long result = 0;
        for (int j = 0; j <= maxVal; j++) {
            result = (result + dp[j]) % MOD;
        }
        
        return (int)result;
    }
}

var countOfPairs = function(nums) {
    const MOD = 1e9 + 7;
    const n = nums.length;
    const maxVal = Math.max(...nums);
    
    // dp[j] 表示当前位置 arr1[i] = j 时的方案数
    let dp = new Array(maxVal + 1).fill(0);
    
    // 初始化第一个位置
    for (let j = 0; j <= nums[0]; j++) {
        dp[j] = 1;
    }
    
    // 动态规划
    for (let i = 1; i < n; i++) {
        const newDp = new Array(maxVal + 1).fill(0);
        const prefixSum = new Array(maxVal + 1).fill(0);
        
        // 计算前缀和
        for (let j = 0; j <= maxVal; j++) {
            prefixSum[j] = (j > 0 ? prefixSum[j-1] : 0) + dp[j];
            prefixSum[j] %= MOD;
        }
        
        for (let j = 0; j <= nums[i]; j++) {
            const minPrev = Math.max(0, j - (nums[i] - nums[i-1]));
            const maxPrev = j;
            
            if (minPrev <= maxPrev) {
                newDp[j] = prefixSum[maxPrev] - (minPrev > 0 ? prefixSum[minPrev-1] : 0);
                newDp[j] = (newDp[j] % MOD + MOD) % MOD;
            }
        }
        
        dp = newDp;
    }
    
    let result = 0;
    for (let j = 0; j <= maxVal; j++) {
        result = (result + dp[j]) % MOD;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n × max_val)
空间复杂度O(max_val)

其中 n 是数组长度，max_val 是数组中的最大值。通过前缀和优化，避免了内层循环，使时间复杂度从 O(n × max_val²) 降到了 O(n × max_val)。