Kimi K2.6思考 LeetCode 3250. 单调数组对的数目 I Java实现

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

核心思路：动态规划 + 前缀和优化。定义 `f[i][j]` 表示前 `i` 个元素组成的单调数组对中，`arr1[i] = j` 的方案数。通过前缀和数组将转移从 O(m^2) 优化到 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();  // nums 中的最大值
        
        // f[i][j]：前 i 个元素，arr1[i] = j 时的单调数组对数目
        int[][] f = new int[n][m + 1];
        
        // 初始化：第 0 个位置，arr1[0] 可以取 0 ~ nums[0] 任意值
        for (int j = 0; j <= nums[0]; ++j) {
            f[0][j] = 1;
        }
        
        // 前缀和数组 g[j] = f[i-1][0] + f[i-1][1] + … + f[i-1][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) {
                // 约束条件：
                // 1. arr1 非递减：j' <= j
                // 2. arr2 非递增：nums[i] – j <= nums[i-1] – j'  =>  j' <= j + nums[i-1] – nums[i]
                int k = Math.min(j, j + nums[i – 1] – nums[i]);
                if (k >= 0) {
                    f[i][j] = g[k];
                }
            }
        }
        
        // 答案：对最后一个位置的所有合法取值求和
        int ans = 0;
        for (int j = 0; j <= nums[n – 1]; ++j) {
            ans = (ans + f[n – 1][j]) % MOD;
        }
        return ans;
    }
}
```

—

核心思路

状态定义
`f[i][j]`：前 `i` 个元素（下标 `0..i`）构成的单调数组对中，`arr1[i] = j` 的方案数。

转移约束
若 `arr1[i] = j`，则 `arr2[i] = nums[i] – j`。要满足单调性：

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

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

前缀和优化
直接枚举 `j'` 是 O(m^2)。用前缀和数组 `g` 预处理 `f[i-1]` 的前缀和，转移变为 O(1)：
f[i][j] = g[\\min(j, j + nums[i-1] – nums[i])]

—

复杂度

指标    复杂度    
时间    O(n \\times m)，其中 m = \\max(nums) \\le 50    
空间    O(n \\times 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[] f = new int[m + 1];
        int[] g = new int[m + 1];
        
        for (int j = 0; j <= nums[0]; ++j) {
            f[j] = 1;
        }
        
        for (int i = 1; i < n; ++i) {
            g[0] = f[0];
            for (int j = 1; j <= m; ++j) {
                g[j] = (g[j – 1] + f[j]) % MOD;
            }
            
            int[] next = 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) {
                    next[j] = g[k];
                }
            }
            f = next;
        }
        
        int ans = 0;
        for (int j = 0; j <= nums[n – 1]; ++j) {
            ans = (ans + f[j]) % MOD;
        }
        return ans;
    }
}
```

参考来源：