---

1121. 将数组分成几个递增序列

• 标签：数组、计数
• 难度：困难

题目链接

• 1121. 将数组分成几个递增序列 - 力扣

题目大意

描述：给定一个非递减（即从小到大，允许相等）的正整数数组 $nums$，和一个整数 $K$。

要求：判断能否把数组分成一个或多个不相交的递增子序列（元素在原数组中的相对顺序不变），并且每个子序列的长度至少为 $K$。能分返回 true，否则返回 false。

说明：

• $1 \le nums.length \le 10^{5}$。
• $1 \le K \le nums.length$。
• $1 \le nums[i] \le 10^{5}$。

示例：

• 示例 1：

输入：nums = [1,2,2,3,3,4,4], K = 3
输出：true
解释：可以分成 [1,2,3,4] 和 [2,3,4] 两个递增序列，每个长度都 ≥ 3。

• 示例 2：

输入：nums = [5,6,6,7,8], K = 3
输出：false
解释：无法满足条件。

解题思路

思路 1：统计最大出现次数

这道题初看可能觉得需要某种复杂的分配策略，但实际上有一个非常巧妙的数学结论。

关键观察：

假设数字 $x$ 在数组中出现了 $cnt$ 次。那么这 $cnt$ 个相同的 $x$ 必须被分配到 $cnt$ 个不同的递增序列中，因为同一个递增序列中不允许有重复的数字。

所以，数组中出现次数最多的那个数字的出现次数 $maxCnt$，决定了我们至少需要 $maxCnt$ 个递增序列。

用人话举个例子：如果数字 2 出现了 5 次，我们必须准备 5 个不同的序列，每个序列里放一个 2。因为不能有两个 2 在同一个递增序列里。

那么，有了 $maxCnt$ 个序列之后，还要求每个序列长度至少为 $K$，总共需要多少个元素？

很简单：至少需要 $maxCnt \times K$ 个元素。如果数组总长度 $n$ 小于这个数，那一定无法满足要求。

所以结论就是：只要 $n \ge maxCnt \times K$，就能成功划分。

为什么这个条件就足够了？
因为一旦我们有了 $maxCnt$ 个序列，并且总元素数足够填满它们到 $K$，总是能找到一种分配方式把剩余的数字分配到这些序列中（因为数组是非递减的，可以把每个数字依次分配到不同的序列中，保证每个序列都是递增的）。

步骤拆解：

1. 统计数组中每个数字出现了多少次，可以用哈希表（Counter）来做。
2. 找到最大的出现次数 $maxCnt$。
3. 判断 $n \ge maxCnt \times K$ 是否成立。

思路 1：代码

class Solution:
    def canDivideIntoSubsequences(self, nums: List[int], k: int) -> bool:
        from collections import Counter
        
        n = len(nums)  # 数组总长度
        
        # 统计每个数字出现的次数
        count = Counter(nums)
        
        # 找到出现次数最多的那个数字的次数
        max_count = max(count.values())
        
        # 判断：总元素数是否 >= 需要的元素数
        # 需要 max_count 个递增序列，每个序列至少 k 个元素
        return n >= max_count * k

思路 1：复杂度分析

• 时间复杂度：$O(n)$。用人话说就是：遍历一次数组统计次数就够了，$n$ 是数组长度。
• 空间复杂度：$O(n)$。哈希表最多需要存 $n$ 个不同的数字。