【算法题】2790. 长度递增组的最大数目-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法题】2790. 长度递增组的最大数目。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目：

给你一个下标从 0 开始、长度为 n 的数组 usageLimits 。

你的任务是使用从 0 到 n - 1 的数字创建若干组，并确保每个数字 i 在所有组中使用的次数总共不超过 usageLimits[i] 次。此外，还必须满足以下条件：

每个组必须由不同的数字组成，也就是说，单个组内不能存在重复的数字。
每个组（除了第一个）的长度必须严格大于前一个组。
在满足所有条件的情况下，以整数形式返回可以创建的最大组数。

示例 1：

输入：usageLimits = [1,2,5]
输出：3
解释：在这个示例中，我们可以使用 0 至多一次，使用 1 至多 2 次，使用 2 至多 5 次。
一种既能满足所有条件，又能创建最多组的方式是：
组 1 包含数字 [2] 。
组 2 包含数字 [1,2] 。
组 3 包含数字 [0,1,2] 。
可以证明能够创建的最大组数是 3 。
所以，输出是 3 。
示例 2：

输入：usageLimits = [2,1,2]
输出：2
解释：在这个示例中，我们可以使用 0 至多 2 次，使用 1 至多 1 次，使用 2 至多 2 次。
一种既能满足所有条件，又能创建最多组的方式是：
组 1 包含数字 [0] 。
组 2 包含数字 [1,2] 。
可以证明能够创建的最大组数是 2 。
所以，输出是 2 。
示例 3：

输入：usageLimits = [1,1]
输出：1
解释：在这个示例中，我们可以使用 0 和 1 至多 1 次。
一种既能满足所有条件，又能创建最多组的方式是：
组 1 包含数字 [0] 。
可以证明能够创建的最大组数是 1 。
所以，输出是 1 。

提示：

1 <= usageLimits.length <= 10^5
1 <= usageLimits[i] <= 10^9文章来源地址https://www.toymoban.com/news/detail-615326.html

java代码：

class Solution {
    public int maxIncreasingGroups(List<Integer> usageLimits) {
        int n = usageLimits.size();
        Collections.sort(usageLimits);
        int[] nums = new int[n];
        for (int i = n - 1 ; i >= 0; i--) {
            nums[n - 1 - i] = usageLimits.get(i);
        }
        int ret = 1;
        int l = 1;
        int r = n;
        while (l < r) {
            int m = l + (r - l) / 2 + 1;
            if (check(nums, m)) {
                l = m;
                ret = Math.max(m, ret);
            } else {
                r = m - 1;
            }
        }
        return ret;
    }
    
    public boolean check(int[] nums, int k) {
        int n = nums.length;
        int d = 0;
        for (int i = 0; i < n; i++) {
            if (Math.max(k - i, 0) <= nums[i]) {
                if (d > 0) {
                    d -= nums[i] - Math.max(k - i, 0);
                }
                continue;
            } 
            d += k - i - nums[i];
        }
        return d <= 0;
    }
}

到了这里，关于【算法题】2790. 长度递增组的最大数目的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！