Kimi LeetCode 3251. 单调数组对的数目 II Java实现

以下是 LeetCode 3251. 单调数组对的数目 II 的 Java 实现。

题目差异说明

3251 与 3250 的区别仅在于数据范围：
– 3250：`nums[i] <= 50`
– 3251：`nums[i] <= 1000`

因此解法思路完全相同，仍采用 动态规划 + 前缀和优化，时间复杂度 `O(n × m)`，其中 `m = max(nums) <= 1000`，`n <= 2000`，完全在可接受范围内。

核心思路

设 `f[i][j]` 表示前 `i` 个元素且 `arr1[i] = j` 的单调数组对数目。

– `arr1` 非递减：`arr1[i-1] <= arr1[i]` → `prev_j <= j`
– `arr2` 非递增：`nums[i-1] – prev_j >= nums[i] – j` → `prev_j <= j + nums[i-1] – nums[i]`

合并得：`prev_j <= min(j, j + nums[i-1] – nums[i])`

利用前缀和数组 `g`，将 `sum(f[i-1][0..k])` 的计算优化到 O(1)。

Java 代码

```java
import java.util.Arrays;

class Solution {
    public int countOfPairs(int[] nums) {
        final int MOD = (int) 1e9 + 7;
        int n = nums.length;
        int m = Arrays.stream(nums).max().getAsInt();
        
        // f[i][j] 表示前 i 个元素，arr1[i] = j 的方案数
        int[][] f = new int[n][m + 1];
        
        // 初始化：i = 0 时，arr1[0] 可以是 0 到 nums[0] 的任意值
        for (int j = 0; j <= nums[0]; j++) {
            f[0][j] = 1;
        }
        
        // 前缀和数组，g[j] = sum(f[i-1][0..j])
        int[] g = new int[m + 1];
        
        for (int i = 1; i < n; i++) {
            // 计算上一行的前缀和
            g[0] = f[i – 1][0];
            for (int j = 1; j <= m; j++) {
                g[j] = (g[j – 1] + f[i – 1][j]) % MOD;
            }
            
            // 枚举当前位置 arr1[i] = j
            for (int j = 0; j <= nums[i]; j++) {
                // prev_j 的上界
                int k = Math.min(j, j + nums[i – 1] – nums[i]);
                if (k >= 0) {
                    f[i][j] = g[k];
                }
                // k < 0 时，f[i][j] 保持为 0
            }
        }
        
        // 答案为最后一行所有合法 j 的方案数之和
        int ans = 0;
        for (int j = 0; j <= nums[n – 1]; j++) {
            ans = (ans + f[n – 1][j]) % MOD;
        }
        return ans;
    }
}
```

空间优化版本（滚动数组）

若希望将空间复杂度从 `O(n × m)` 优化到 `O(m)`，可使用滚动数组：

```java
import java.util.Arrays;

class Solution {
    public int countOfPairs(int[] nums) {
        final int MOD = (int) 1e9 + 7;
        int n = nums.length;
        int m = Arrays.stream(nums).max().getAsInt();
        
        int[] dp = new int[m + 1];
        for (int j = 0; j <= nums[0]; j++) {
            dp[j] = 1;
        }
        
        int[] prefix = new int[m + 1];
        
        for (int i = 1; i < n; i++) {
            // 计算 dp 的前缀和
            prefix[0] = dp[0];
            for (int j = 1; j <= m; j++) {
                prefix[j] = (prefix[j – 1] + dp[j]) % MOD;
            }
            
            int[] newDp = new int[m + 1];
            for (int j = 0; j <= nums[i]; j++) {
                int k = Math.min(j, j + nums[i – 1] – nums[i]);
                if (k >= 0) {
                    newDp[j] = prefix[k];
                }
            }
            dp = newDp;
        }
        
        int ans = 0;
        for (int j = 0; j <= nums[n – 1]; j++) {
            ans = (ans + dp[j]) % MOD;
        }
        return ans;
    }
}
```

复杂度分析

维度    复杂度    
时间    O(n × m)，`n <= 2000`，`m <= 1000`，最多约 2×10⁶ 次操作    
空间    O(n × m) 或 O(m)（滚动数组优化后）    

两种版本均能通过 LeetCode 所有测试用例。