长度递增组的最大数目

难度: Hard

给你一个下标从 0 开始、长度为 n 的数组 usageLimits 。

你的任务是使用从 0 到 n - 1 的数字创建若干组，并确保每个数字 i 在 所有组 中使用的次数总共不超过 usageLimits[i] 次。此外，还必须满足以下条件：

每个组必须由不同的数字组成，也就是说，单个组内不能存在重复的数字。
每个组（除了第一个）的长度必须 严格大于 前一个组。

在满足所有条件的情况下，以整数形式返回可以创建的最大组数。

示例 1：

输入：usageLimits = [1,2,5]
输出：3
解释：在这个示例中，我们可以使用 0 至多一次，使用 1 至多 2 次，使用 2 至多 5 次。
一种既能满足所有条件，又能创建最多组的方式是： 
组 1 包含数字 [2] 。
组 2 包含数字 [1,2] 。
组 3 包含数字 [0,1,2] 。 
可以证明能够创建的最大组数是 3 。 
所以，输出是 3 。

示例 2：

输入：usageLimits = [2,1,2]
输出：2
解释：在这个示例中，我们可以使用 0 至多 2 次，使用 1 至多 1 次，使用 2 至多 2 次。
一种既能满足所有条件，又能创建最多组的方式是： 
组 1 包含数字 [0] 。 
组 2 包含数字 [1,2] 。
可以证明能够创建的最大组数是 2 。 
所以，输出是 2 。

示例 3：

输入：usageLimits = [1,1]
输出：1
解释：在这个示例中，我们可以使用 0 和 1 至多 1 次。 
一种既能满足所有条件，又能创建最多组的方式是：
组 1 包含数字 [0] 。
可以证明能够创建的最大组数是 1 。 
所以，输出是 1 。

提示：

1 <= usageLimits.length <= 10⁵
1 <= usageLimits[i] <= 10⁹

Submission

运行时间: 151 ms

内存: 30.7 MB

class Solution:
    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:
        ul = sorted(usageLimits)
        remain = 0 # 前面数组多余的数量
        require = 1 # 最小目标序列需要的长度，从1~n
        for num in ul:
            remain += num
            if remain >= require: # 如果当前位置积累的数量达到了目标序列的要求
                remain -= require 
                require += 1 
        return require - 1

Explain

该题解采用贪心算法的思路。首先将usageLimits数组排序，这样可以保证我们在构建组的过程中，优先使用使用次数较少的数字。然后，我们使用一个变量remain来记录在构建当前组之前，数组中剩余的总使用次数。变量require用于记录当前组需要达到的最小长度。我们遍历排序后的数组，不断累加每个数字的使用次数到remain中，并检查是否满足当前组的长度要求（即remain >= require）。如果满足，我们就可以构建一个新的组，然后更新remain和require的值，继续构建下一个组。最后，返回构建的组数。

时间复杂度: O(nlogn)

空间复杂度: O(n)

class Solution:
    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:
        ul = sorted(usageLimits) # 对usageLimits进行排序
        remain = 0 # 前面数组多余的数量
        require = 1 # 最小目标序列需要的长度，从1开始
        for num in ul: # 遍历排序后的数组
            remain += num # 累加当前数字的使用次数
            if remain >= require: # 如果当前累积的数量达到了目标序列的要求
                remain -= require # 更新剩余数量
                require += 1 # 更新下一个组的长度要求
        return require - 1 # 返回构建的组数

Explore

贪心算法在这个问题中的选用是因为它可以在每一步做出局部最优选择，即优先使用使用次数最少的数字，从而简化问题并提高效率。如果使用动态规划，可能需要构造一个复杂的状态转移方程来处理所有可能的组合，这可能导致时间和空间复杂度显著增加。回溯算法同样会涉及到大量的递归调用和状态回退，可能在处理大数据集时效率不高。因此，贪心算法在这种情况下提供了一个更为高效且实现简洁的解决方案。

在算法实现中，每个数字的使用次数累加到变量`remain`中，并通过构建新的组来逐步消耗这些累积的使用次数。排序`usageLimits`只是为了优化组的构建过程，确保每次都是使用最小的可用数字。在构建组时，我们从累积的总次数`remain`中减去当前组所需的最小长度`require`，这样就能保证每个数字的使用次数不会超过其在`usageLimits`中的原始限制，因为我们是按照从小到大的顺序使用它们的。

如果`usageLimits`数组中存在大量相同的值，这通常意味着我们可以构建多个长度相同的组，因为我们每次都会尽可能多地使用相同的值来满足当前组的要求。这种情况下，组数可能会受到影响，因为相同值的大量存在可能会允许构建更多的组，尤其是当这些值足够大以支持多个递增长度的组时。总体而言，这会增加可构建的组数，因为相同的高频值提供了更多的灵活性来满足不同组的需求。

在算法中，`remain`表示累积的数字使用次数，而`require`是构建下一个组所需的最小长度。通过减去`require`而不是重置`remain`，我们可以保留过多累积的次数并用于构建后续的组。这种做法允许连续的组构建，不浪费任何数字的使用次数，提高了数字利用率。如果直接重置`remain`，则每次构建完一个组后，过剩的数量将被抛弃，这可能导致无法构建更多本可以通过累积次数达成的组。