当前位置：首页 > news >正文

【Leetcode 每日一题】3250. 单调数组对的数目 I

news 来源：原创 2025/5/18 9:58:31

问题背景

给你一个长度为 $n$ 的正整数数组 $n u m s$ 。
如果两个非负整数数组 $arr_1, arr_2)$ 满足以下条件，我们称它们是单调数组对：
两个数组的长度都是 $n$ 。

$arr_1$ 是单调 非递减 的，换句话说 $arr_1[0] \le arr_1[1] \le ... \le arr_1[n - 1]$ 。
$arr_2$ 是单调 非递增 的，换句话说 $arr_2[0] \le arr_2[1] \le ... \le arr_2[n - 1]$ 。
对于所有的 $\le i \le n - 1$ 都有 $arr_1[i] + arr_2[i] == nums[i]$ 。

请你返回所有单调数组对的数目。
由于答案可能很大，请你将它对 $10 ^ 9 + 7$ 取余后返回。

数据约束

$\le n = nums.length \le 2000$
$\le nums[i] \le 50$

解题过程

周赛三四题的水准，两道题目只在数据规模上有差异，目前只能尝试写灵神题解的解释。
这题虽然对两个数组有要求，但是实际上只需要枚举其中一个数组的情况，把对另外一个数组中元素的要求当成约束就行。
根据动态规划缩小问题规模的思想：

原问题是下标 $0$ 到 $n - 1$ 中的单调数组对的个数，且 $arr_1[n−1] = j = 0, 1, 2, ..., nums[n - 1]$ 。
子问题是下标 $0$ 到 $i$ 中的单调数组对的个数，且 $arr_1[i] = j$ ，将其记作 $d p [i] [j]$ 。

用 $k$ 表示 $arr_1[i−1]$ ，那么根据约束条件： $\ \begin{cases} arr_1[i - 1] \le arr_1[i] \\ arr_2[i - 1] \ge arr_2[i] \\ \end{cases}$ ，即 $\ \begin{cases} k \le j \\ nums[i - 1] - k \ge nums[i] - j \\ \end{cases}$ ，可以得到 $k$ 的上界。
解得 $\le min(j, nums[i - 1] - nums[i] + j) = j + min(nums[i - 1] - nums[i], 0)$ ，由于所有数组中的元素都是非负的，而 $nums[i] = arr_1[i] + arr_2[i]$ ，所以 $\le nums[i - 1]$ 。
记 $ma x K = j + min (n u m s [i - 1] - n u m s [i], 0)$ ，那么 $\begin{cases} 0，& maxK \lt 0 \\ \mathop{\Sigma} \limits _ {k = 0} ^ {maxK} dp[i - 1][k]，& maxK \ge 0 \\ \end{cases}$ 。
这里 $\mathop{\Sigma} \limits _ {k = 0} ^ {maxK} dp[i - 1][k]$ 表示对所有的 $k$ 从 $0$ 到 $ma x K$ 的情况，求下标 $0$ 到 $i - 1$ 中的单调数组对的个数之和，要求 $arr_1 = k$ 。这显然满足前缀和的定义，记 $\mathop{\Sigma} \limits _ {k = 0} ^ {j} dp[i - 1][k]$ ，那么上述状态转移方程 $(3)$ 可以简化为 $\begin{cases} 0，& maxK \lt 0 \\ s[maxK]，& maxK \ge 0 \\ \end{cases}$ 。
初始值 $d p [0] [j] = 1$ ，其中 $j = 0, 1, 2, ..., n u m s [0]$ 。这表示的是，下标 $0$ 到 $0$ 中的单调数组对的个数，也就是只考虑数组中第一个元素的情况， $arr_1[i]$ 可以是合法范围内任意值。

后续还有进一步优化，目前一下子掌握不了，先暂时放弃。

具体实现

class Solution {// 根据题意定义模数private static final int MOD = 1000000007;public int countOfPairs(int[] nums) {int n = nums.length;// m 表示 nums 数组中的最大值，所有数组中的元素都不会超过这个范围，也就是应枚举的最大值int m = Arrays.stream(nums).max().getAsInt();long [][] dp = new long[n][m + 1];long[] preSum = new long[m + 1];// 填充初始值，只考虑数组中第一个元素的情况Arrays.fill(dp[0], 0, nums[0] + 1, 1);for(int i = 1; i < n; i++) {// 计算前缀和，这是它的定义preSum[0] = dp[i - 1][0];for(int k = 1; k <= m; k++) {preSum[k] = (preSum[k - 1] + dp[i - 1][k]) % MOD;}for(int j = 0; j <= nums[i]; j++) {int maxK = j + Math.min(nums[i - 1] - nums[i], 0);dp[i][j] = maxK >= 0 ? preSum[maxK] % MOD : 0;}}// 答案是考虑完数组中最后一个元素之后，对所有可能情形求和return (int) (Arrays.stream(dp[n - 1], 0, nums[n - 1] + 1).sum() % MOD);}
}

问题背景

数据约束

解题过程

具体实现

相关文章：