LeetCode 题解工作台
单调数组对的数目 II
给你一个长度为 n 的 正 整数数组 nums 。 如果两个 非负 整数数组 (arr1, arr2) 满足以下条件，我们称它们是 单调 数组对： 两个数组的长度都是 n 。 arr1 是单调 非递减 的，换句话说 arr1[0] 。 arr2 是单调 非递增 的，换句话说 arr2[0] >= a…
5
题型
5
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们定义 表示下标 的单调数组对的数目，且 $arr1[i] = j$。初始时 $[i][j] = 0$，答案为 $\sum_{j=0}^{\textit{nums}[n-1]} f[n-1][j]$。 当 $i = 0$ 时，有 $[0][j] = 1$，其中 $0 \leq j \leq \textit{nums}[0]$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个长度为 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] <= 1000
解题思路
方法一：动态规划 + 前缀和优化
我们定义 表示下标 的单调数组对的数目，且 。初始时 ，答案为 。
当 时，有 ，其中 。
当 时，我们可以根据 计算 。由于 是单调非递减的，因此 。又由于 是单调非递增的，因此 。即 。
答案为 。
时间复杂度 ，空间复杂度 。其中 表示数组 的长度，而 表示数组 中的最大值。
class Solution:
def countOfPairs(self, nums: List[int]) -> int:
mod = 10**9 + 7
n, m = len(nums), 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]))
for j in range(nums[i] + 1):
k = min(j, j + nums[i - 1] - nums[i])
if k >= 0:
f[i][j] = s[k] % mod
return sum(f[-1][: nums[-1] + 1]) % mod
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate demonstrates an understanding of dynamic programming and combinatorics as applied to array problems.
- question_mark
The candidate is able to optimize brute-force solutions using more efficient techniques like prefix sums.
- question_mark
The candidate's explanation of complexity and trade-offs shows awareness of both time and space optimization.
常见陷阱
外企场景- error
Failing to optimize the brute force approach leads to excessive time complexity.
- error
Incorrectly handling duplicate elements in the array, which may lead to overcounting or undercounting pairs.
- error
Misunderstanding the monotonic condition, which could lead to counting invalid pairs.
进阶变体
外企场景- arrow_right_alt
Handling arrays with duplicates more efficiently.
- arrow_right_alt
Optimizing for arrays with a small number of elements.
- arrow_right_alt
Applying a divide-and-conquer approach to improve performance on large arrays.