What is the main idea behind counting monotonic pairs in this problem?

The core idea is using a DP table dp[i][s] where each state represents the number of monotonic pairs ending with a specific value, ensuring transitions maintain monotonicity.

Can this problem handle arrays with maximum length 2000 efficiently?

Yes, with state transition DP and prefix sums, the algorithm scales to n = 2000 without timing out.

Why do we use prefix sums in the DP solution?

Prefix sums allow cumulative updates efficiently, avoiding O(n^2) inner loops when summing valid previous states.

Are repeated numbers in nums handled differently?

Repeated numbers are naturally handled in the DP state; the transitions include counts from previous identical values without violating monotonicity.

Is the state transition dynamic programming pattern common in combinatorial array problems?

Yes, this pattern efficiently counts sequences or pairs under constraints and is a key approach for monotonic pair counting like in this problem.

#3250

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

单调数组对的数目 I

给你一个长度为 n 的正整数数组 nums 。如果两个非负整数数组 (arr1, arr2) 满足以下条件，我们称它们是单调数组对：两个数组的长度都是 n 。 arr1 是单调非递减的，换句话说 arr1[0] 。 arr2 是单调非递增的，换句话说 arr2[0] >= a…

数组数学动态规划组合数学前缀和

题目描述

给你一个长度为 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⁹ + 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 <= 2000
1 <= nums[i] <= 50

lightbulb

解题思路

方法一：动态规划 + 前缀和优化

我们定义 $f[i][j]$ 表示下标 $[0,..i]$ 的单调数组对的数目，且 $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]$ 。

当 $i > 0$ 时，我们可以根据 $f[i-1][j']$ 计算 $f[i][j]$ 。由于 $\textit{arr1}$ 是单调非递减的，因此 $j' \leq j$ 。又由于 $\textit{arr2}$ 是单调非递增的，因此 $\textit{nums}[i] - j \leq \textit{nums}[i - 1] - j'$ 。即 $j' \leq \min(j, j + \textit{nums}[i - 1] - \textit{nums}[i])$ 。

答案为 $\sum_{j=0}^{\textit{nums}[n-1]} f[n-1][j]$ 。

时间复杂度 $O(n \times m)$ ，空间复杂度 $O(n \times m)$ 。其中 $n$ 表示数组 $\textit{nums}$ 的长度，而 $m$ 表示数组 $\textit{nums}$ 中的最大值。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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

speed

复杂度分析

指标	值
时间	complexity depends on n and the maximum nums[i] value due to DP iterations and prefix sums, roughly O(n * maxValue). Space complexity is O(n * maxValue) for the DP table.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if candidate correctly defines dp[i][s] and understands state transitions.
question_mark
Observe whether prefix sums are used to optimize the cumulative counts in DP.
question_mark
Watch for correct handling of repeated elements and monotonic constraints.

warning

常见陷阱

外企场景

error
Forgetting to enforce monotonicity when updating DP states.
error
Inefficiently iterating without prefix sums, leading to timeouts.
error
Incorrectly summing final DP values, missing some valid pairs.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Counting strictly increasing monotonic pairs instead of non-decreasing.
arrow_right_alt
Finding monotonic triples or larger tuples with similar DP approach.
arrow_right_alt
Applying the DP state transition pattern to other bounded integer arrays with combinatorial constraints.

help

常见问题

外企场景

继续练习

#3251 单调数组对的数目 II #3312 查询排序后的最大公约数 #3179 K 秒后第 N 个元素的值