跳转至

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 <= 105
  • 1 <= usageLimits[i] <= 109

解法

方法一：贪心

思考

第 \(k\) 组需要 \(k\) 个两两不同的数，且每个数 \(i\) 至多用 \(usageLimits[i]\) 次，求最多组数。直接枚举组数再分配额度需要匹配。

限额升序后从左消耗：累计剩余额度一旦够开第 \(k+1\) 组就开一组并扣掉 \(k+1\)，余量滚入下一个限额。贪心保证先用掉较小配额，组数尽量多。

将限额从小到大排序后依次累加。每多出一个可用额度，就尝试多开一组；能开则把该组消耗从累计中扣掉。最终组数即为答案。

时间复杂度 \(O(n \times \log n)\)，空间复杂度 \(O(\log n)\)。其中 \(n\) 是数组长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:
        usageLimits.sort()
        k, n = 0, len(usageLimits)
        for i in range(n):
            if usageLimits[i] > k:
                k += 1
                usageLimits[i] -= k
            if i + 1 < n:
                usageLimits[i + 1] += usageLimits[i]
        return k

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public int maxIncreasingGroups(List<Integer> usageLimits) {
        Collections.sort(usageLimits);
        int k = 0;
        long s = 0;
        for (int x : usageLimits) {
            s += x;
            if (s > k) {
                ++k;
                s -= k;
            }
        }
        return k;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int maxIncreasingGroups(vector<int>& usageLimits) {
        sort(usageLimits.begin(), usageLimits.end());
        int k = 0;
        long long s = 0;
        for (int x : usageLimits) {
            s += x;
            if (s > k) {
                ++k;
                s -= k;
            }
        }
        return k;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func maxIncreasingGroups(usageLimits []int) int {
    sort.Ints(usageLimits)
    s, k := 0, 0
    for _, x := range usageLimits {
        s += x
        if s > k {
            k++
            s -= k
        }
    }
    return k
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
function maxIncreasingGroups(usageLimits: number[]): number {
    usageLimits.sort((a, b) => a - b);
    let k = 0;
    let s = 0;
    for (const x of usageLimits) {
        s += x;
        if (s > k) {
            ++k;
            s -= k;
        }
    }
    return k;
}

评论