题目重点：降序排序寻找最后合法排名，解释阈值单调性和截断桶的线性优化。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 评分非负整数，k可为0，空输入输出0。
- “k个”表示至少能选择k项，不要求恰好k项达到阈值。
解题路线
- 降序排序后检查第k项是否≥k。成立时前k项都达标，失败时达到k的项不足k个，后面的更大k也不可能成立。
- 扫描rank=1..n，合法则更新，首次失败停止。最大阈值≤n，评分特别大也不能让k超出实例数量。
- 另一表述count(score≥k)≥k有单调真前缀，可对k二分；但每次全扫描会O(n log n)，不比当前排序渐进更优。
- 若想线性时间，所有score>n截到n，用n+1桶。从k=n降到0累计≥k的个数，首次累计≥k即答案。空间O(n)，大评分不必按最大score开巨大桶。
手动走一遍
训练[3,0,6,1,5]排序[6,5,3,1,0]，第三项3≥3、第四项1<4，答案3；[100,100]答案2，不是100。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def maximum_rating_threshold(ratings):
if any(r < 0 for r in ratings):
raise ValueError("ratings must be nonnegative")
answer = 0
for rank,value in enumerate(sorted(ratings,reverse=True),1):
if value < rank:
break
answer = rank
return answer
复杂度
排序O(n log n)时间、O(n)示例空间；桶O(n)时间与空间。
易错点与追问
容易失分的边界
- 把评分之和当阈值。
- 按0起始下标漏掉rank+1。
- 要求恰好k项达标误排除高分更多的情况。
继续深挖
- 实例评分持续增减如何维护阈值？
- 只允许O(1)辅助空间有哪些取舍？
- 评分是实数时桶合同怎么改？
