What is the key pattern for Maximum Number of Groups Entering a Competition?

The problem primarily uses binary search over the valid answer space combined with greedy assignment of students.

Can we form groups without sorting grades?

Sorting helps guarantee that smaller grades can fill initial groups, simplifying the validation of non-decreasing sums and group sizes.

How do we know a group count is valid?

A candidate group count is valid if students can be assigned incrementally so each group has more students than the previous and higher total grades.

What is the time complexity of this solution?

Sorting takes O(n log n) and binary search with validation takes O(log n * n), resulting in overall O(n log n) efficiency.

Does the binary search guarantee the maximum number of groups?

Yes, binary search narrows down to the largest number of groups where the assignment rules hold, ensuring an optimal solution.

#2358

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

分组的最大数量

给你一个正整数数组 grades ，表示大学中一些学生的成绩。你打算将所有学生分为一些有序的非空分组，其中分组间的顺序满足以下全部条件：第 i 个分组中的学生总成绩小于第 (i + 1) 个分组中的学生总成绩，对所有组均成立（除了最后一组）。第 i 个分组中的学生总数小于第 (i…

数组数学二分查找贪心

题目描述

给你一个正整数数组 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⁵

lightbulb

解题思路

方法一：贪心 + 二分查找

我们观察题目中的条件，第 $i$ 组的学生人数要小于第 $i+1$ 组的学生人数，且第 $i$ 组的学生总成绩要小于第 $i+1$ 组的学生总成绩，我们只需要将学生按照成绩从小到大排序，然后每一组依次分配 $1$ , $2$ , ..., $k$ 个学生即可。如果最后一组的学生人数不足 $k$ 个，那么我们可以将这些学生分配到前面的最后一组中。

因此，我们要找到最大的 $k$ ，使得 $\frac{(1 + k) \times k}{2} \leq n$ ，其中 $n$ 为学生的总人数。我们可以使用二分查找来求解。

我们定义二分查找的左边界为 $l = 1$ ，右边界为 $r = n$ ，每一次二分查找的中点为 $mid = \lfloor \frac{l + r + 1}{2} \rfloor$ ，如果 $(1 + mid) \times mid \gt 2 \times n$ ，则说明 $mid$ 太大，我们需要将右边界缩小至 $mid - 1$ ，否则我们需要将左边界增大至 $mid$ 。

最后，我们将 $l$ 作为答案返回即可。

时间复杂度 $O(\log n)$ ，空间复杂度 $O(1)$ 。其中 $n$ 为学生的总人数。

1

2

3

4

5

class Solution:
    def maximumGroups(self, grades: List[int]) -> int:
        n = len(grades)
        return bisect_right(range(n + 1), n * 2, key=lambda x: x * x + x) - 1

speed

复杂度分析

指标	值
时间	complexity is O(n log n + log n * n) due to sorting and binary search checks over group counts. Space complexity is O(1) beyond input storage, as the validation uses constant extra space.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Sorting grades can simplify grouping checks.
question_mark
Binary search may hint at optimizing the number of groups.
question_mark
Tracking cumulative group sizes ensures valid non-decreasing sequences.

warning

常见陷阱

外企场景

error
Failing to sort grades first increases complexity and may miss valid groupings.
error
Not enforcing that each group has more students than the previous group leads to incorrect counts.
error
Checking only sums without tracking group sizes can produce invalid configurations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Limit group sum differences to a maximum value.
arrow_right_alt
Allow only contiguous student sequences for groups.
arrow_right_alt
Change constraints so each group must have strictly increasing sum by at least a fixed delta.

help

常见问题

外企场景

继续练习

#2601 质数减法运算 #2790 长度递增组的最大数目 #2967 使数组成为等数数组的最小代价