长度递增组的最大数目

You are given a 0-indexed array usageLimits of length n.

Your task is to create groups using numbers from 0 to n - 1, ensuring that each number, i, is used no more than usageLimits[i] times in total across all groups. You must also satisfy the following conditions:

• Each group must consist of distinct numbers, meaning that no duplicate numbers are allowed within a single group.
• Each group (except the first one) must have a length strictly greater than the previous group.

Return an integer denoting the maximum number of groups you can create while satisfying these conditions.

 

Example 1:

Input: usageLimits = [1,2,5]
Output: 3
Explanation: In this example, we can use 0 at most once, 1 at most twice, and 2 at most five times.
One way of creating the maximum number of groups while satisfying the conditions is: 
Group 1 contains the number [2].
Group 2 contains the numbers [1,2].
Group 3 contains the numbers [0,1,2]. 
It can be shown that the maximum number of groups is 3. 
So, the output is 3. 

Example 2:

Input: usageLimits = [2,1,2]
Output: 2
Explanation: In this example, we can use 0 at most twice, 1 at most once, and 2 at most twice.
One way of creating the maximum number of groups while satisfying the conditions is:
Group 1 contains the number [0].
Group 2 contains the numbers [1,2].
It can be shown that the maximum number of groups is 2.
So, the output is 2. 

Example 3:

Input: usageLimits = [1,1]
Output: 1
Explanation: In this example, we can use both 0 and 1 at most once.
One way of creating the maximum number of groups while satisfying the conditions is:
Group 1 contains the number [0].
It can be shown that the maximum number of groups is 1.
So, the output is 1. 

 

Constraints:

• 1 <= usageLimits.length <= 105
• 1 <= usageLimits[i] <= 109

/*
 * 思路：
 * 使用Java Stream API来简化代码。我们可以通过流操作来计算每个组的大小并更新每个数字的使用次数。
 * 具体步骤：
 * 1. 将数组转换为一个流并降序排序。
 * 2. 逐步增加组的大小，每次从流中取出所需的元素，更新其使用次数。
 * 3. 通过过滤和映射来更新和筛选出可用的数字。
 */

import java.util.Arrays;

public class Solution {
    public int maxGroups(int[] usageLimits) {
        Arrays.sort(usageLimits);
        int n = usageLimits.length;
        int maxGroups = 0;
        int groupSize = 1;

        while (groupSize <= n) {
            int finalGroupSize = groupSize;
            long count = Arrays.stream(usageLimits)
                                .filter(usage -> usage >= finalGroupSize)
                                .count();

            if (count < groupSize) {
                break;
            }

            maxGroups++;
            for (int i = 0; i < n; i++) {
                if (usageLimits[i] >= groupSize) {
                    usageLimits[i] -= groupSize;
                    groupSize++;
                }
            }
        }
        return maxGroups;
    }
}

该题解采用贪心算法的思路。首先将usageLimits数组排序，这样可以保证我们在构建组的过程中，优先使用使用次数较少的数字。然后，我们使用一个变量remain来记录在构建当前组之前，数组中剩余的总使用次数。变量require用于记录当前组需要达到的最小长度。我们遍历排序后的数组，不断累加每个数字的使用次数到remain中，并检查是否满足当前组的长度要求（即remain >= require）。如果满足，我们就可以构建一个新的组，然后更新remain和require的值，继续构建下一个组。最后，返回构建的组数。

O(nlogn)

O(n)