Medium

题目描述

给你一个正整数数组 grades，表示大学中学生的成绩。你想将所有这些学生分成有序的非空组，使得分组满足以下条件：

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

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

示例 1：

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

示例 2：

输入：grades = [8,8]
输出：1
解释：我们只能形成 1 组，因为形成 2 组会导致两组的学生人数相等。

约束：

  • 1 <= grades.length <= 10^5
  • 1 <= grades[i] <= 10^5

解题思路

这道题的关键洞察是：为了形成最多的组，我们需要贪心地构造尽可能小的组。

首先分析题目要求：

  1. 后一组的成绩总和要大于前一组
  2. 后一组的人数要大于前一组

基本思路是先对数组排序，然后按照 1, 2, 3, … 的人数分组。排序后，由于每组内部都选择最小的成绩，这样能最大化后续组的成绩总和。

有两种主要解法：

解法一：模拟分组（贪心）

  • 排序后按照 1, 2, 3, … 的人数依次分组
  • 检查每组的成绩总和是否严格递增
  • 如果不满足条件则停止分组

解法二：数学公式（推荐） 通过数学分析可以发现，对于 n 个学生，最多可以分成 k 组，其中 k 满足： 1 + 2 + 3 + ... + k ≤ n，即 k(k+1)/2 ≤ n

这是因为排序后，按 1, 2, 3, … 分组总是能保证成绩总和递增的最优策略。我们只需要找到最大的 k 使得三角数不超过 n。

解法二更高效，时间复杂度从 O(n log n) 降到 O(√n)。

代码实现

class Solution {
public:
    int maximumGroups(vector<int>& grades) {
        int n = grades.size();
        int k = 0;
        while ((k + 1) * (k + 2) / 2 <= n) {
            k++;
        }
        return k;
    }
};

class Solution:
    def maximumGroups(self, grades: List[int]) -> int:
        n = len(grades)
        k = 0
        while (k + 1) * (k + 2) // 2 <= n:
            k += 1
        return k

public class Solution {
    public int MaximumGroups(int[] grades) {
        int n = grades.Length;
        int k = 0;
        while ((k + 1) * (k + 2) / 2 <= n) {
            k++;
        }
        return k;
    }
}

var maximumGroups = function(grades) {
    const n = grades.length;
    let k = 0;
    while ((k + 1) * (k + 2) / 2 <= n) {
        k++;
    }
    return k;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度备注
数学公式O(√n)O(1)推荐解法
贪心模拟O(n log n)O(1)需要排序

相关题目