class Solution {
public:
int countOfPairs(vector<int>& nums) {
}
};
100395. 单调数组对的数目 I
给你一个长度为 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] 。请你返回所有 单调 数组对的数目。
由于答案可能很大，请你将它对 109 + 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] <= 50相似题目
原站题解
golang 解法, 执行用时: 15 ms, 内存消耗: 4.5 MB, 提交时间: 2024-08-12 09:56:17
// 前缀和dp
func countOfPairs1(nums []int) (ans int) {
const mod = 1_000_000_007
n := len(nums)
m := slices.Max(nums)
f := make([][]int, n)
for i := range f {
f[i] = make([]int, m+1)
}
s := make([]int, m+1)
for j := 0; j <= nums[0]; j++ {
f[0][j] = 1
}
for i := 1; i < n; i++ {
s[0] = f[i-1][0]
for k := 1; k <= m; k++ {
s[k] = s[k-1] + f[i-1][k] // f[i-1] 的前缀和
}
for j := 0; j <= nums[i]; j++ {
maxK := j + min(nums[i-1]-nums[i], 0)
if maxK >= 0 {
f[i][j] = s[maxK] % mod
}
}
}
for _, v := range f[n-1][:nums[n-1]+1] {
ans += v
}
return ans % mod
}
// 优化，压缩第一维
func countOfPairs2(nums []int) (ans int) {
const mod = 1_000_000_007
n := len(nums)
m := nums[n-1]
f := make([]int, m+1)
for j := range f[:min(nums[0], m)+1] {
f[j] = 1
}
for i := 1; i < n; i++ {
for j := 1; j <= m; j++ {
f[j] += f[j-1] // 计算前缀和
}
j0 := max(nums[i]-nums[i-1], 0)
for j := min(nums[i], m); j >= j0; j-- {
f[j] = f[j-j0] % mod
}
clear(f[:min(j0, m+1)])
}
for _, v := range f {
ans += v
}
return ans % mod
}
// 进一步优化
func countOfPairs(nums []int) (ans int) {
const mod = 1_000_000_007
n := len(nums)
m := nums[n-1]
f := make([]int, m+1)
for j := range f[:min(nums[0], m)+1] {
f[j] = 1
}
for i := 1; i < n; i++ {
j0 := max(nums[i]-nums[i-1], 0)
m2 := min(nums[i], m)
if j0 > m2 {
return 0
}
for j := 1; j <= m2-j0; j++ {
f[j] = (f[j] + f[j-1]) % mod // 计算前缀和
}
copy(f[j0:m2+1], f)
clear(f[:j0])
}
for _, v := range f {
ans += v
}
return ans % mod
}
java 解法, 执行用时: 3 ms, 内存消耗: 43.6 MB, 提交时间: 2024-08-12 09:53:05
class Solution {
private static final int MOD = 1_000_000_007;
private static final int MX = 3001; // MAX_N + MAX_M = 2000 + 1000 = 3000
private static final long[] F = new long[MX]; // f[i] = i!
private static final long[] INV_F = new long[MX]; // inv_f[i] = i!^-1
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;
}
}
cpp 解法, 执行用时: 21 ms, 内存消耗: 30.8 MB, 提交时间: 2024-08-12 09:52:38
class Solution {
public:
int countOfPairs1(vector<int>& nums) {
const int MOD = 1'000'000'007;
int n = nums.size();
int m = ranges::max(nums);
vector<vector<long long>> f(n, vector<long long>(m + 1));
vector<long long> s(m + 1);
fill(f[0].begin(), f[0].begin() + nums[0] + 1, 1);
for (int i = 1; i < n; i++) {
partial_sum(f[i - 1].begin(), f[i - 1].end(), s.begin()); // f[i-1] 的前缀和
for (int j = 0; j <= nums[i]; j++) {
int max_k = j + min(nums[i - 1] - nums[i], 0);
f[i][j] = max_k >= 0 ? s[max_k] % MOD : 0;
}
}
return reduce(f[n - 1].begin(), f[n - 1].begin() + nums[n - 1] + 1, 0LL) % MOD;
}
int countOfPairs2(vector<int>& nums) {
const int MOD = 1'000'000'007;
int n = nums.size(), m = nums.back();
vector<int> f(m + 1);
fill(f.begin(), f.begin() + min(nums[0], m) + 1, 1);
for (int i = 1; i < n; i++) {
for (int j = 1; j <= m; j++) {
f[j] = (f[j] + f[j - 1]) % MOD; // 计算前缀和
}
int j0 = max(nums[i] - nums[i - 1], 0);
for (int j = min(nums[i], m); j >= j0; j--) {
f[j] = f[j - j0];
}
fill(f.begin(), f.begin() + min(j0, m + 1), 0);
}
return reduce(f.begin(), f.end(), 0LL) % MOD;
}
int countOfPairs(vector<int>& nums) {
const int MOD = 1'000'000'007;
int n = nums.size(), m = nums[n - 1];
vector<int> f(m + 1);
fill(f.begin(), f.begin() + min(nums[0], m) + 1, 1);
for (int i = 1; i < n; i++) {
int j0 = max(nums[i] - nums[i - 1], 0);
int m2 = min(nums[i], m);
if (j0 > m2) {
return 0;
}
for (int j = 1; j <= m2 - j0; j++) {
f[j] = (f[j] + f[j - 1]) % MOD; // 计算前缀和
}
copy(f.begin(), f.begin() + m2 - j0 + 1, f.begin() + j0);
fill(f.begin(), f.begin() + j0, 0);
}
return reduce(f.begin(), f.end(), 0LL) % MOD;
}
};
python3 解法, 执行用时: 49 ms, 内存消耗: 16.5 MB, 提交时间: 2024-08-12 09:50:25
# 前缀和优化dp
class Solution:
def countOfPairs1(self, nums: List[int]) -> int:
MOD = 1_000_000_007
n = len(nums)
m = max(nums)
f = [[0] * (m + 1) for _ in range(n)]
for j in range(nums[0] + 1):
f[0][j] = 1
for i in range(1, n):
s = list(accumulate(f[i - 1])) # f[i-1] 的前缀和
for j in range(nums[i] + 1):
max_k = j + min(nums[i - 1] - nums[i], 0)
f[i][j] = s[max_k] % MOD if max_k >= 0 else 0
return sum(f[-1][:nums[-1] + 1]) % MOD
# 空间优化
def countOfPairs2(self, nums: List[int]) -> int:
MOD = 1_000_000_007
m = nums[-1]
f = [0] * (m + 1)
for j in range(min(nums[0], m) + 1):
f[j] = 1
for pre, cur in pairwise(nums):
for j in range(1, m + 1):
f[j] += f[j - 1] # 计算前缀和
j0 = max(cur - pre, 0)
for j in range(min(cur, m), j0 - 1, -1):
f[j] = f[j - j0] % MOD
for j in range(min(j0, m + 1)):
f[j] = 0
return sum(f) % MOD
# 进一步优化
def countOfPairs3(self, nums: List[int]) -> int:
MOD = 1_000_000_007
m = nums[-1]
f = [0] * (m + 1)
for j in range(min(nums[0], m) + 1):
f[j] = 1
for pre, cur in pairwise(nums):
j0 = max(cur - pre, 0)
m2 = min(cur, m)
if j0 > m2:
return 0
for j in range(1, m2 - j0 + 1):
f[j] = (f[j] + f[j - 1]) % MOD # 计算前缀和
f[j0: m2 + 1] = f[:m2 - j0 + 1]
f[:j0] = [0] * j0
return sum(f) % MOD
# 组合数学
def countOfPairs(self, nums: List[int]) -> int:
MOD = 1_000_000_007
m = nums[-1]
for x, y in pairwise(nums):
m -= max(y - x, 0)
return comb(m + len(nums), m) % MOD if m >= 0 else 0