题目描述
思路解析
一句话答案：LeetCode 2358 分组的最大数量：分成有序几组、后组人数与总成绩递增，求最多组数。二分答案：升序切块让总成绩自动成立，只看人数——最大 k 使 k(k+1)/2 ≤ n，在 0~n 二分，O(log n) 时间、O(1) 空间。
分组要同时满足人数和总成绩递增，求的是什么
把学生按成绩分成有序几组，要求后一组人数比前一组多、后一组总成绩也更高，返回最多能分几组。人数除不尽也不碍事：多出的学生并进最后一组即可——只要求人数严格递增，末组更大不违规。题面 grades=[10,6,12,7,3,5] 有 6 个人，答案是 3（人数 1、2、3 三组）；换成 grades=[8,8] 只两人，硬分两组人数就相等，最多 1 组。
为什么『后一组总成绩更高』这条根本不用管
先把成绩从小到大排好，再从左往右一块块切给各组：第一组拿最小的几个，第二组往后拿更多。后一组人数更多，且每人成绩都不小于前一组任何人——人更多、每个还不更小，总成绩必然更大。所以人数一严格递增，总成绩就自动跟着递增，成绩的具体数值不影响答案，干脆全扔掉、只盯人数。
问题缩成：最大的 k 使 k(k+1)/2 ≤ n
人数要严格递增，分成 k 组最省人的排法就是 1、2、3、…、k 一路加一，共要 k(k+1)/2 个人（三角数）。只要它不超过 n 就一定分得出来。所以能否分成 k 组等价于 k(k+1)/2 ≤ n，答案就是让它成立的最大 k。题面 n 是 6 时 1+2+3=6 恰好用完可分 3 组；再加一组要 10 个人就凑不齐。
逐个试 k 太慢，怎么换成二分
n 能到十万，从 k 取 1 逐个往上试，最坏试到答案那档，白扫一截。好在 k(k+1)/2 随 k 单调变大，所有 k 被切成两半：小的都 ≤ n、大的都超 n，答案正是分界上最后一个满足的 k。这种不套公式、而是猜一个 k 用 k(k+1)/2 ≤ n 验一验再往一边收的思路，就是二分答案（二分的是答案本身，不是下标）。参考代码两边乘 2 成 k²+k ≤ 2n，bisect_right 在 range(n+1) 上按 key x²+x 找第一个超过 2n 的位置，减 1 即最大可行 k。下面演算用手写 l、r 二分展开，bisect_right 就是它的库函数封装。
题面 6 个人这组，二分三轮各砍向哪半
总人数 6，两倍即 2n=12，在 0 到 6 间找最大的 k 使 k²+k ≤ 12。左界 l 起于 0、右界 r 起于 6。第一轮中点向上取整取 3，3²+3=12 不超 12，分 3 组可行、这个中点可能就是答案，把 l 拉到 3。第二轮 [3,6] 中点取 5，5²+5=30 超 12，分 5 组人不够，r 退到 4。第三轮 [3,4] 中点取 4，4²+4=20 仍超 12，r 压到 3。此时 l、r 都停在 3，二分结束，答案 3，正是前面切出的三组。
等号一丢、中点取整一错，答案就少一组
别真在成绩上凑总成绩——切块后它自动成立。等号也别丢：n 是 6 时 T(3) 正好等于 6，人刚好用完仍可行，写成严格小于会把这组判没、答案少一组。手写二分还藏个暗坑：找『最大可行』时中点要向上取整、配 l=mid 与 r=mid−1；若向下取整，区间剩两格时中点永远卡左端、l 推不动，就死循环。复杂度上，答案只由人数 n 定、不遍历成绩数组，时间 O(log n)、空间 O(1)。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这句:只要人数 1,2,3,... 严格递增,总成绩自动跟着递增,答案就是最大的 k 使 1+2+...+k ≤ n。下面分三段演给你看。
先看原始的 6 个成绩,乱序排着。直接盯着成绩去凑「总成绩递增」很难,我们换个角度:先把成绩从小到大排好。
升序排好后是 [3,5,6,7,10,12]。接下来从左往右切:第 1 组拿 1 个人,第 2 组拿 2 个人,第 3 组拿 3 个人,人数严格递增。看看总成绩会不会自动跟着涨。
第 1 组从左边接着拿 1 个人,拿到的是 [3]。蓝色是前面已经分好的组。
第 1 组总成绩 3。它是第一组,先记着,和下一组比。
第 2 组从左边接着拿 2 个人,拿到的是 [5, 6]。蓝色是前面已经分好的组。
第 2 组总成绩 11,比上一组的 3 大。注意我们根本没刻意去凑,只因为这组人更多、每个人成绩都不小于上一组,总和自然更高。
第 3 组从左边接着拿 3 个人,拿到的是 [7, 10, 12]。蓝色是前面已经分好的组。
第 3 组总成绩 29,比上一组的 11 大。注意我们根本没刻意去凑,只因为这组人更多、每个人成绩都不小于上一组,总和自然更高。
三组都切好了:人数 1、2、3 严格递增,总成绩 3、11、29 也严格递增,两个条件全满足。可见「总成绩」这条根本没拦住我们,真正的瓶颈只是「人数够不够凑出严格递增」。
既然只跟人数有关,干脆把成绩全扔掉。这排格子代表候选组数 k,从 1 开始逐个试:分 k 组至少要 1+2+...+k 个人,记成 T(k)。只要 T(k) 不超过总人数 6,这个 k 就可行。
试 k = 1:至少要 1 = 1 个人。不超过 6,可行,标绿。继续看更大的 k。
试 k = 2:至少要 1+2 = 3 个人。不超过 6,可行,标绿。继续看更大的 k。
试 k = 3:至少要 1+2+3 = 6 个人。正好等于 6,人刚好用完,仍然可行,标绿。继续看更大的 k。
试 k = 4:至少要 1+2+3+4 = 10 个人,已经超过 6 了,凑不出来,标红。既然 T(k) 只增不减,再大的 k 更不可能,到此为止。最后一个绿色的 k = 3 就是答案。
逐个试当然行,但 n 能到十万,得用二分。把条件 k(k+1)/2 ≤ n 两边乘 2,写成 k²+k ≤ 2n,这里 2n = 12。在 0 到 6 之间二分,找最大的满足它的 k。
区间 [0, 6],中点向上取整 mid = 3。算 3²+3 = 12,和 12 比:不超过,说明分 3 组可行,这个 mid 本身可以成为答案。
因为可行,把下界 l 拉到 3,绿色候选也跟着到 3。答案至少 3,还想更大,所以去 mid 右边接着找。
区间 [3, 6],中点向上取整 mid = 5。算 5²+5 = 30,和 12 比:超过了,分 5 组人不够,mid 及它右边都不行。
因为不可行,把上界 r 压到 mid - 1 = 4,mid 和它右边整段排除。区间越缩越小。
区间 [3, 4],中点向上取整 mid = 4。算 4²+4 = 20,和 12 比:超过了,分 4 组人不够,mid 及它右边都不行。
因为不可行,把上界 r 压到 mid - 1 = 3,mid 和它右边整段排除。区间越缩越小。
l 和 r 碰头都停在 3,二分结束。绿色格 3 就是最大能分的组数,答案 = 3,和前面一块一块切出来的 3 组完全对上。
边界都在三角数上卡:1 人 1 组、2 人 1 组、3 人 2 组、10 人 4 组,记住 T(k)=k(k+1)/2 逐个套即可。
抓住两点:总成绩条件靠升序切块自动满足;组数就是让 k(k+1)/2 ≤ n 的最大 k。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *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复杂度
- 时间：O(log n)，在 0..n 上二分,每次砍一半
- 空间：O(1)，只用 l、r、mid 几个变量
易错点
面试追问把动画讲成自己的话
追问为什么可以完全不管「总成绩递增」这个条件?
追问为什么最大组数就是最大的 k 使 k(k+1)/2 ≤ n?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
按位或最大的最小子数组长度
LeetCode 2411 · 中等 · 沿着 二分套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题