分组的最大数量

难度: Medium

给你一个正整数数组 grades ，表示大学中一些学生的成绩。你打算将所有学生分为一些有序的非空分组，其中分组间的顺序满足以下全部条件：

第 i 个分组中的学生总成绩小于第 (i + 1) 个分组中的学生总成绩，对所有组均成立（除了最后一组）。
第 i 个分组中的学生总数小于第 (i + 1) 个分组中的学生总数，对所有组均成立（除了最后一组）。

返回可以形成的最大组数。

示例 1：

输入：grades = [10,6,12,7,3,5]
输出：3
解释：下面是形成 3 个分组的一种可行方法：
- 第 1 个分组的学生成绩为 grades = [12] ，总成绩：12 ，学生数：1
- 第 2 个分组的学生成绩为 grades = [6,7] ，总成绩：6 + 7 = 13 ，学生数：2
- 第 3 个分组的学生成绩为 grades = [10,3,5] ，总成绩：10 + 3 + 5 = 18 ，学生数：3 
可以证明无法形成超过 3 个分组。

示例 2：

输入：grades = [8,8]
输出：1
解释：只能形成 1 个分组，因为如果要形成 2 个分组的话，会导致每个分组中的学生数目相等。

提示：

1 <= grades.length <= 10⁵
1 <= grades[i] <= 10⁵

Submission

运行时间: 35 ms

内存: 26.3 MB

class Solution:
    def maximumGroups(self, grades: List[int]) -> int:
        
        ans=0
        i=1
        n=len(grades)
        while(n>=i):
            n-=i
            i+=1
            ans+=1
        return ans

Explain

题解的核心思路是从数学角度分析问题。首先，为了使每个分组的总成绩和总人数都严格递增，可以让每个分组包含的学生数目按最小可能增长，即第1个分组1个学生，第2个分组2个学生，依此类推。这种分组方法使得每个后续分组可以包含更多的学生，从而有更大的可能性达到更高的总成绩。实现中，我们从1开始计数，尽可能多地形成分组，每次迭代减少可用的学生数（即数组的长度n），并逐步增加下一个分组需要的学生数，直到剩余的学生数不足以形成下一个分组。这样得到的分组数量就是可能的最大分组数。

时间复杂度: O(√n)

空间复杂度: O(1)

class Solution:
    def maximumGroups(self, grades: List[int]) -> int:
        # ans为最终的分组数
        ans = 0
        # i表示当前分组应包含的学生数
        i = 1
        # n为剩余可分配的学生数
        n = len(grades)
        # 循环直到剩余学生数不足以形成新的分组
        while n >= i:
            n -= i  # 从剩余学生数中减去当前分组的学生数
            i += 1  # 增加下一个分组的学生数
            ans += 1  # 增加分组计数
        return ans

Explore

在本题中，我们的目标是最大化分组的数量，而不是考虑成绩的具体分配。因此，我们只需要确保每个分组的学生数量递增，这样就自然满足了题目要求每个分组的总人数严格递增。至于成绩的排序，它并不影响分组数量的最大化，因为题目并没有要求每个分组的成绩必须基于学生的实际成绩排序。

题解的方法确保了每个分组的学生数量是递增的，但并没有直接确保每个分组的总成绩也递增。然而，题目的核心并不要求成绩递增，只要求分组的人数递增。实际上，如果需要考虑成绩递增，我们可能需要调整分组方式，确保每个分组选择的学生使得成绩最优化，但这超出了当前题目的要求。

在题解中，变量 `i` 表示当前分组应该包含的学生数目。循环每进行一次，`i` 就递增，表示下一个分组应包含更多的学生。循环终止条件 `n >= i` 确保当前剩余的学生数 `n` 足够形成一个包含 `i` 个学生的新分组。当 `n` 小于 `i` 时，说明剩余的学生数不足以按当前规则形成一个完整的分组，因此循环停止，此时的分组数量就是可能的最大分组数。

在每次循环中，`n -= i` 代表从总的学生数中减去当前分组应含的学生数，这样更新剩余可用的学生数。这一步是为了保持每个分组的学生数目递增，而不是随机分配。`i += 1` 则确保下一个分组的学生数比当前分组多一个，这样就能满足题目要求的每个分组的人数必须严格递增的条件。这两步操作共同工作，以确保尽可能多地形成符合条件的分组，从而最大化分组数量。