3251. 单调数组对的数目 II(2323)
给你一个长度为 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 <= 20001 <= nums[i] <= 1000
记忆化搜索：记忆化搜索无法利用到前缀和的优化，导致多了一层的时间复杂度，超时
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
int MOD = (int)1e9+7;
public int countOfPairs(int[] nums) {
int n = nums.length;
HashMap<Integer, Integer> memo = new HashMap<>();
return dfs(0, 0, nums, memo);
}
public int dfs(int i, int min, int nums[], HashMap<Integer, Integer> memo) {
int n = nums.length;
if (i == n-1) return Math.max(nums[i]-min+1, 0);
if (memo.containsKey(n*min + i)) return memo.get(n*min + i);
long res = 0;
for (int j = min; j <= nums[i]; j++) {
res += dfs(i+1, Math.max(j, j+nums[i+1]-nums[i]), nums, memo);
}
res %= MOD;
memo.put(n*min + i, (int)res);
return (int)res;
}
}
|
前缀和dp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
int MOD = (int)1e9+7;
public int countOfPairs(int[] nums) {
int n = nums.length;
int m = Arrays.stream(nums).max().getAsInt();
int f[][] = new int[n+1][m+1];
Arrays.fill(f[0], 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j <= nums[i]; j++) {
int diff = i > 0 ? nums[i-1] - nums[i] : 0;
int i_max = j + Math.min(0, diff);
if (i_max >= 0) f[i+1][j] = f[i][i_max];
if (j-1 >= 0) f[i+1][j] = (f[i+1][j]+f[i+1][j-1]) % MOD;
}
}
return f[n][nums[n-1]];
}
}
|
组合数解法
参考 灵神题解
首先来看一个特殊的情况：所有 nums[i] 都相同。例如示例 2，nums=[5,5,5,5]，在所有元素都相同的情况下，只要 arr1 是单调非递减的，那么 arr2 就一定是单调非递增的。
要向上走 5 步，向右走 4 步，一共走 5+4=9 步。选择其中 4 步向右走，于是问题变成从 9 步中选 4 步的方案数，即 C(9,4)=126
以 m=nums[n−1] 为基准，如果所有元素都等于 m，那么问题等价于从 m+n 步中选 n 步的方案数，即 C(m+n,n)
如果 a[i−1]=x, a[i]=y，那么必须满足 x≤y 且 nums[i−1]−x≥nums[i]−y，即
y≥max(x,x+nums[i]−nums[i−1])
用路径来理解，就是在 i 这个位置向右走之前，要「强制性」地向上走 d 步
剩下的 m+n−d 步可以随意安排向右走还是向上走。于是问题变成从 m+n−d 步中选 n 步向右走的方案数，即 C(m+n−d,n)
总之就是，这个问题可以转换成计算组合数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| class Solution {
private static final int MOD = 1_000_000_007;
private static final int MX = 3001;
private static final long[] F = new long[MX];
private static final long[] INV_F = new long[MX];
static {
F[0] = 1;
for (int i = 1; i < MX; i++) {
F[i] = F[i - 1] * i % MOD;
}
INV_F[MX - 1] = pow(F[MX - 1], MOD - 2);
for (int i = MX - 1; i > 0; i--) {
INV_F[i - 1] = INV_F[i] * i % MOD;
}
}
public int countOfPairs(int[] nums) {
int n = nums.length;
int m = nums[n - 1];
for (int i = 1; i < n; i++) {
m -= Math.max(nums[i] - nums[i - 1], 0);
if (m < 0) {
return 0;
}
}
return (int) comb(m + n, n);
}
private long comb(int n, int m) {
return F[n] * INV_F[m] % MOD * INV_F[n - m] % MOD;
}
private static long pow(long x, int n) {
long res = 1;
for (; n > 0; n /= 2) {
if (n % 2 > 0) {
res = res * x % MOD;
}
x = x * x % MOD;
}
return res;
}
}
|
