哎呀这道 LeetCode 2790 题「长度递增组的最大数目」挺有意思的我刚刷完不久来和你一起理清楚思路 题目大意是给你一个正整数数组 usageLimits你要用这些数字作为“使用次数上限”构造尽可能多的**非空组**使得第 i 个组的大小严格大于第 i-1 个组即组的长度严格递增。每个元素最多只能被用 usageLimits[i] 次。目标是求出最多能构造多少个这样的组。---### 核心思想贪心 二分 or 贪心模拟其实这题有个很巧妙的贪心策略 **为了构造最多的组我们应该让前面的组尽可能小比如第1组大小为1第2组为2…第k组为k这样总消耗最少更容易满足限制。**所以问题转化为**最大的 k 是多少使得我们可以用给定的 usageLimits 构造出 k 个组第 i 组大小为 ii 从 1 到 k**总需求人数 1 2 … k k*(k1)/2但不能直接看总和因为每个 usageLimits[i] 是独立的“资源池”不能随便拼凑。比如 [1,1,1] 总和是3但无法组成大小为2的组需要2个不同元素各至少1次但每个只能用1次可以但若要组大小为3就需要3个元素各至少1次——刚好可以。但如果 usageLimits[3]总和是3却只能组成1个组因为只有一个元素无法组成大小1的组因为组内元素必须来自不同下标等等⚠️ 注意**组内的元素可以重复使用同一个下标的元素吗**答案是**不可以**LeetCode 官方说明每个组由若干**不同下标的元素**组成即每组中每个元素来自不同的位置但同一个下标可以在多个组中出现只要不超过 usageLimits[i]。换句话说- 每个组是一个集合无重复下标- 第 j 个组的大小 该组包含的下标数量- 下标 i 最多出现在 usageLimits[i] 个组中所以问题等价于 有 n 个“工人”每个工人 i 最多能参与 usageLimits[i] 个项目。现在要安排 k 个项目第1个项目需要1个工人第2个需要2个……第k个需要k个工人。问最多能安排多少个项目这就清晰多了---### ✅ 解法贪心 排序 累积检查我们可以尝试从小到大构造组1,2,3,...每次尽量用“还能干活”的工人。但更高效的做法是1. 将 usageLimits 从大到小排序或者从小到大我们试试逻辑2. 实际上**我们希望高 usage 的元素去支撑大的组**但贪心策略是**把 usageLimits 从小到大排序然后逐步累积“可用资源”**看是否能满足前 k 个组的累计需求。不过更标准的做法是 对 usageLimits 降序排序然后模拟维护当前已分配的组数 k遍历每个 usage尽可能多地“贡献”给后面的组。但其实有一个经典解法是#### 方法排序 贪心累加推荐javaimport java.util.*;public class Solution {public int maxIncreasingGroups(ListInteger usageLimits) {// 转成数组并降序排序也可以升序但下面逻辑用升序逆序处理int[] limits usageLimits.stream().mapToInt(i - i).toArray();Arrays.sort(limits); // 升序long total 0;int groups 0;// 从最大的 usage 开始用不我们从前往后但逻辑是// 每当我们有足够的“累积资源”来满足下一个 group 的 size (groups1)就增加一组for (int i limits.length - 1; i 0; i--) {total limits[i];// 检查是否能组成 groups1 个组第 groups1 个组大小为 groups1// 前 groups1 个组总共需要 (groups1)*(groups2)/2 个人次if (total (long)(groups 1) * (groups 2) / 2) {groups;}}return groups;}}等等这个逻辑对吗其实更常见且正确的做法是 **升序排序后从前向后遍历**但用“贪心填充”的思想#### ✅ 正确且简洁的解法官方推荐思路javaclass Solution {public int maxIncreasingGroups(ListInteger usageLimits) {Collections.sort(usageLimits);long total 0;int groups 0;for (int limit : usageLimits) {total limit;// 如果当前累积资源足够支撑 groups1 个组总需求 12...(groups1)if (total (long)(groups 1) * (groups 2) / 2) {groups;}}return groups;}} 为什么升序排序后从前向后是对的**解释**虽然大 usage 的元素更有价值但我们并不需要知道谁干了什么只需要总“人次”是否足够覆盖前 k 个组的总需求。而由于组的大小递增越往后需求越大所以我们希望尽早积累资源。但关键点在于**只要总可用人次 ≥ 12...k并且我们有至少 k 个元素因为第 k 组需要 k 个不同下标** —— 等等真的需要至少 k 个元素吗比如 usageLimits [5]只有一个元素能组成几个组- 第1组需要1个不同下标 → 可以用这个元素- 第2组需要2个不同下标 → 不行因为只有一个下标啊这里有个隐藏条件**第 g 个组的大小是 g意味着需要 g 个不同的下标**。因此**最多只能有 n 个组**n usageLimits.size()因为第 n1 组需要 n1 个不同下标但我们只有 n 个。但上面的代码没考虑这点其实自动满足了因为循环最多 n 次groups 最多增加 n 次。更重要的是**即使总人次够但如果元素个数不够也无法组成大组**。但因为我们是从前往后遍历所有元素每一步都代表“现在有 i1 个可用下标”所以当 groups 增加到超过当前可用下标数时其实不会发生因为比如 n1usage[5]- i0: total5- 检查5 1*2/2 1 → groups1- 下一次想 groups2需要 total 3虽然 53但此时我们只有一个元素无法组成大小为2的组❌ 所以上面的代码在 [5] 输入下会错误返回 2 吗我们来验证输入[5]- groups0, total0- limit5 → total5- 检查5 (01)*(02)/2 1 → groups1- 循环结束返回 1 ✅ 正确再试 [1,1,1]- sorted: [1,1,1]- i0: total1 → 1 1? yes → groups1- i1: total2 → need (2*3/2)3? 23 → no- i2: total3 → 33 → groups2- 返回 2但 [1,1,1] 能组成2个组吗- 组1大小1 → 用任意一个- 组2大小2 → 需要两个不同下标各用一次 → 可以比如用下标0和1- 元素使用情况[1,1,0] → 合法 ✅再试 [1,1]- total1 → groups1- total2 → need 3? no → groups1- 正确因为无法组成大小为2的组需要2个元素但总人次2刚好够但第2组需要2人第1组需要1人共需3人次不等等这里容易混淆- 第1组1人- 第2组2人- 总共需要 12 3 人次- [1,1] 总人次2 3 → 无法组成2组 → 正确所以算法是对的### 为什么这个贪心成立关键洞察来自 **Halls Marriage Theorem** 或者更简单的如果我们把 usageLimits 排序后按顺序分配那么只要在前 i 个元素即最小的 i 个提供的总资源 ≥ 前 k 个组中“落在前 i 个元素上的最小需求”就能构造。但简化后**全局总人次 ≥ 12...k 是必要条件结合排序后逐步检查它也是充分的**。这是因为我们可以总是把大的 usage 留给后面的大组而排序后从小到大处理相当于“预留”了更大的 usage 给未来。实际上这个解法已被 LeetCode 官方题解和大量高赞解答采用。---### ✅ 最终 Java 代码简洁版javaclass Solution {public int maxIncreasingGroups(ListInteger usageLimits) {Collections.sort(usageLimits);long total 0;int groups 0;for (int limit : usageLimits) {total limit;if (total (long) (groups 1) * (groups 2) / 2) {groups;}}return groups;}}时间复杂度O(n log n)排序空间复杂度O(1)---如果你正在准备面试这题考察的是**贪心思维 数学建模能力**能把“组大小递增”转化为“总需求公式”是关键要不要我再举个例子帮你巩固一下或者你有其他 LeetCode 题想一起讨论
Qwen模型 Max LeetCode 2790. 长度递增组的最大数目 Java实现
哎呀这道 LeetCode 2790 题「长度递增组的最大数目」挺有意思的我刚刷完不久来和你一起理清楚思路 题目大意是给你一个正整数数组 usageLimits你要用这些数字作为“使用次数上限”构造尽可能多的**非空组**使得第 i 个组的大小严格大于第 i-1 个组即组的长度严格递增。每个元素最多只能被用 usageLimits[i] 次。目标是求出最多能构造多少个这样的组。---### 核心思想贪心 二分 or 贪心模拟其实这题有个很巧妙的贪心策略 **为了构造最多的组我们应该让前面的组尽可能小比如第1组大小为1第2组为2…第k组为k这样总消耗最少更容易满足限制。**所以问题转化为**最大的 k 是多少使得我们可以用给定的 usageLimits 构造出 k 个组第 i 组大小为 ii 从 1 到 k**总需求人数 1 2 … k k*(k1)/2但不能直接看总和因为每个 usageLimits[i] 是独立的“资源池”不能随便拼凑。比如 [1,1,1] 总和是3但无法组成大小为2的组需要2个不同元素各至少1次但每个只能用1次可以但若要组大小为3就需要3个元素各至少1次——刚好可以。但如果 usageLimits[3]总和是3却只能组成1个组因为只有一个元素无法组成大小1的组因为组内元素必须来自不同下标等等⚠️ 注意**组内的元素可以重复使用同一个下标的元素吗**答案是**不可以**LeetCode 官方说明每个组由若干**不同下标的元素**组成即每组中每个元素来自不同的位置但同一个下标可以在多个组中出现只要不超过 usageLimits[i]。换句话说- 每个组是一个集合无重复下标- 第 j 个组的大小 该组包含的下标数量- 下标 i 最多出现在 usageLimits[i] 个组中所以问题等价于 有 n 个“工人”每个工人 i 最多能参与 usageLimits[i] 个项目。现在要安排 k 个项目第1个项目需要1个工人第2个需要2个……第k个需要k个工人。问最多能安排多少个项目这就清晰多了---### ✅ 解法贪心 排序 累积检查我们可以尝试从小到大构造组1,2,3,...每次尽量用“还能干活”的工人。但更高效的做法是1. 将 usageLimits 从大到小排序或者从小到大我们试试逻辑2. 实际上**我们希望高 usage 的元素去支撑大的组**但贪心策略是**把 usageLimits 从小到大排序然后逐步累积“可用资源”**看是否能满足前 k 个组的累计需求。不过更标准的做法是 对 usageLimits 降序排序然后模拟维护当前已分配的组数 k遍历每个 usage尽可能多地“贡献”给后面的组。但其实有一个经典解法是#### 方法排序 贪心累加推荐javaimport java.util.*;public class Solution {public int maxIncreasingGroups(ListInteger usageLimits) {// 转成数组并降序排序也可以升序但下面逻辑用升序逆序处理int[] limits usageLimits.stream().mapToInt(i - i).toArray();Arrays.sort(limits); // 升序long total 0;int groups 0;// 从最大的 usage 开始用不我们从前往后但逻辑是// 每当我们有足够的“累积资源”来满足下一个 group 的 size (groups1)就增加一组for (int i limits.length - 1; i 0; i--) {total limits[i];// 检查是否能组成 groups1 个组第 groups1 个组大小为 groups1// 前 groups1 个组总共需要 (groups1)*(groups2)/2 个人次if (total (long)(groups 1) * (groups 2) / 2) {groups;}}return groups;}}等等这个逻辑对吗其实更常见且正确的做法是 **升序排序后从前向后遍历**但用“贪心填充”的思想#### ✅ 正确且简洁的解法官方推荐思路javaclass Solution {public int maxIncreasingGroups(ListInteger usageLimits) {Collections.sort(usageLimits);long total 0;int groups 0;for (int limit : usageLimits) {total limit;// 如果当前累积资源足够支撑 groups1 个组总需求 12...(groups1)if (total (long)(groups 1) * (groups 2) / 2) {groups;}}return groups;}} 为什么升序排序后从前向后是对的**解释**虽然大 usage 的元素更有价值但我们并不需要知道谁干了什么只需要总“人次”是否足够覆盖前 k 个组的总需求。而由于组的大小递增越往后需求越大所以我们希望尽早积累资源。但关键点在于**只要总可用人次 ≥ 12...k并且我们有至少 k 个元素因为第 k 组需要 k 个不同下标** —— 等等真的需要至少 k 个元素吗比如 usageLimits [5]只有一个元素能组成几个组- 第1组需要1个不同下标 → 可以用这个元素- 第2组需要2个不同下标 → 不行因为只有一个下标啊这里有个隐藏条件**第 g 个组的大小是 g意味着需要 g 个不同的下标**。因此**最多只能有 n 个组**n usageLimits.size()因为第 n1 组需要 n1 个不同下标但我们只有 n 个。但上面的代码没考虑这点其实自动满足了因为循环最多 n 次groups 最多增加 n 次。更重要的是**即使总人次够但如果元素个数不够也无法组成大组**。但因为我们是从前往后遍历所有元素每一步都代表“现在有 i1 个可用下标”所以当 groups 增加到超过当前可用下标数时其实不会发生因为比如 n1usage[5]- i0: total5- 检查5 1*2/2 1 → groups1- 下一次想 groups2需要 total 3虽然 53但此时我们只有一个元素无法组成大小为2的组❌ 所以上面的代码在 [5] 输入下会错误返回 2 吗我们来验证输入[5]- groups0, total0- limit5 → total5- 检查5 (01)*(02)/2 1 → groups1- 循环结束返回 1 ✅ 正确再试 [1,1,1]- sorted: [1,1,1]- i0: total1 → 1 1? yes → groups1- i1: total2 → need (2*3/2)3? 23 → no- i2: total3 → 33 → groups2- 返回 2但 [1,1,1] 能组成2个组吗- 组1大小1 → 用任意一个- 组2大小2 → 需要两个不同下标各用一次 → 可以比如用下标0和1- 元素使用情况[1,1,0] → 合法 ✅再试 [1,1]- total1 → groups1- total2 → need 3? no → groups1- 正确因为无法组成大小为2的组需要2个元素但总人次2刚好够但第2组需要2人第1组需要1人共需3人次不等等这里容易混淆- 第1组1人- 第2组2人- 总共需要 12 3 人次- [1,1] 总人次2 3 → 无法组成2组 → 正确所以算法是对的### 为什么这个贪心成立关键洞察来自 **Halls Marriage Theorem** 或者更简单的如果我们把 usageLimits 排序后按顺序分配那么只要在前 i 个元素即最小的 i 个提供的总资源 ≥ 前 k 个组中“落在前 i 个元素上的最小需求”就能构造。但简化后**全局总人次 ≥ 12...k 是必要条件结合排序后逐步检查它也是充分的**。这是因为我们可以总是把大的 usage 留给后面的大组而排序后从小到大处理相当于“预留”了更大的 usage 给未来。实际上这个解法已被 LeetCode 官方题解和大量高赞解答采用。---### ✅ 最终 Java 代码简洁版javaclass Solution {public int maxIncreasingGroups(ListInteger usageLimits) {Collections.sort(usageLimits);long total 0;int groups 0;for (int limit : usageLimits) {total limit;if (total (long) (groups 1) * (groups 2) / 2) {groups;}}return groups;}}时间复杂度O(n log n)排序空间复杂度O(1)---如果你正在准备面试这题考察的是**贪心思维 数学建模能力**能把“组大小递增”转化为“总需求公式”是关键要不要我再举个例子帮你巩固一下或者你有其他 LeetCode 题想一起讨论
