LeetCode 题解工作台
长度递增组的最大数目
给你一个下标从 0 开始、长度为 n 的数组 usageLimits 。 你的任务是使用从 0 到 n - 1 的数字创建若干组，并确保每个数字 i 在 所有组 中使用的次数总共不超过 usageLimits[i] 次。此外，还必须满足以下条件： 每个组必须由 不同 的数字组成，也就是说，单个组内不…
5
题型
5
代码语言
3
相关题
当前训练重点
困难 · 二分·搜索·答案·空间
答案摘要
class Solution: def maxIncreasingGroups(self, usageLimits: List[int]) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
给你一个下标从 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 <= 1051 <= usageLimits[i] <= 109
解题思路
方法一
class Solution:
def maxIncreasingGroups(self, usageLimits: List[int]) -> int:
usageLimits.sort()
k, n = 0, len(usageLimits)
for i in range(n):
if usageLimits[i] > k:
k += 1
usageLimits[i] -= k
if i + 1 < n:
usageLimits[i + 1] += usageLimits[i]
return k
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Can the candidate efficiently apply binary search over the possible answer space?
- question_mark
Is the candidate comfortable using a greedy approach to validate group formation?
- question_mark
Does the candidate optimize the solution using sorting for easier greedy implementation?
常见陷阱
外企场景- error
Failing to correctly implement binary search over the valid answer space can lead to inefficient solutions.
- error
Not handling edge cases where the group sizes or the usage limits are very small or large.
- error
Ignoring the importance of sorting the `usageLimits` array to facilitate the greedy approach.
进阶变体
外企场景- arrow_right_alt
Handling different ranges of `usageLimits` values to see how the solution scales.
- arrow_right_alt
Optimizing the solution further using advanced techniques, such as dynamic programming.
- arrow_right_alt
Exploring alternative greedy approaches for edge cases where the binary search may not be optimal.