Hard

题目描述

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

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

  • 每个分组必须由不同的数字组成，这意味着在单个分组内不允许重复的数字。
  • 每个分组（除了第一个）的长度必须严格大于前一个分组。

返回在满足这些条件下你可以创建的最大分组数量。

示例 1：

输入：usageLimits = [1,2,5]
输出：3
解释：在这个例子中，我们最多可以使用 0 一次，1 两次，2 五次。
创建最大数量分组的一种方法是：
分组 1 包含数字 [2]。
分组 2 包含数字 [1,2]。
分组 3 包含数字 [0,1,2]。
可以证明最大分组数量是 3。
所以输出是 3。

示例 2：

输入：usageLimits = [2,1,2]
输出：2
解释：在这个例子中，我们最多可以使用 0 两次，1 一次，2 两次。
创建最大数量分组的一种方法是：
分组 1 包含数字 [0]。
分组 2 包含数字 [1,2]。
可以证明最大分组数量是 2。
所以输出是 2。

示例 3：

输入：usageLimits = [1,1]
输出：1
解释：在这个例子中，我们最多可以使用 0 和 1 各一次。
创建最大数量分组的一种方法是：
分组 1 包含数字 [0]。
可以证明最大分组数量是 1。
所以输出是 1。

约束条件：

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

解题思路

这是一道典型的二分搜索 + 贪心算法题目。核心思路是：

问题分析：

  • 我们要创建若干个分组，分组长度严格递增（1, 2, 3, …, k）
  • 每个数字 i 最多能使用 usageLimits[i] 次
  • 每个分组内的数字必须不同

解决方案：

  1. 排序优化：将 usageLimits 按升序排序，使用次数少的数字优先分配给较小的分组
  2. 二分搜索：对分组数量进行二分搜索，范围是 [1, n]
  3. 贪心验证：对于给定的分组数量 k，贪心地检查是否可行：
    • 第 1 组需要 1 个数字，第 2 组需要 2 个数字，…，第 k 组需要 k 个数字
    • 从使用次数最少的数字开始分配，尽量让每个数字的使用次数不超过其限制

验证逻辑： 对于分组数量 k，我们需要总共 1+2+…+k = k*(k+1)/2 个数字位置。按排序后的顺序，第 i 个数字最多可以使用 usageLimits[i] 次。我们贪心地让每个数字尽可能多地被使用，但不超过其限制和所需的总数量。

代码实现

class Solution {
public:
    int maxIncreasingGroups(vector<int>& usageLimits) {
        sort(usageLimits.begin(), usageLimits.end());
        
        int left = 1, right = usageLimits.size();
        int result = 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canMakeGroups(usageLimits, mid)) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
    
private:
    bool canMakeGroups(vector<int>& usageLimits, int k) {
        long long needed = (long long)k * (k + 1) / 2;
        long long available = 0;
        
        for (int limit : usageLimits) {
            available += min((long long)limit, (long long)k);
            if (available >= needed) return true;
        }
        
        return false;
    }
};

class Solution:
    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:
        usageLimits.sort()
        
        def canMakeGroups(k):
            needed = k * (k + 1) // 2
            available = 0
            
            for limit in usageLimits:
                available += min(limit, k)
                if available >= needed:
                    return True
            
            return False
        
        left, right = 1, len(usageLimits)
        result = 1
        
        while left <= right:
            mid = (left + right) // 2
            if canMakeGroups(mid):
                result = mid
                left = mid + 1
            else:
                right = mid - 1
        
        return result

public class Solution {
    public int MaxIncreasingGroups(IList<int> usageLimits) {
        var limits = usageLimits.ToArray();
        Array.Sort(limits);
        
        int left = 1, right = limits.Length;
        int result = 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (CanMakeGroups(limits, mid)) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
    
    private bool CanMakeGroups(int[] usageLimits, int k) {
        long needed = (long)k * (k + 1) / 2;
        long available = 0;
        
        foreach (int limit in usageLimits) {
            available += Math.Min(limit, k);
            if (available >= needed) return true;
        }
        
        return false;
    }
}

var maxIncreasingGroups = function(usageLimits) {
    usageLimits.sort((a, b) => a - b);
    
    const canMakeGroups = (k) => {
        const needed = k * (k + 1) / 2;
        let available = 0;
        
        for (const limit of usageLimits) {
            available += Math.min(limit, k);
            if (available >= needed) return true;
        }
        
        return false;
    };
    
    let left = 1, right = usageLimits.length;
    let result = 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (canMakeGroups(mid)) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度排序 + 二分搜索解法
时间复杂度O(n log n + n log n) = O(n log n)
空间复杂度O(1) 或 O(n)（取决于排序实现）

其中 n 是 usageLimits 数组的长度。排序需要 O(n log n) 时间，二分搜索进行 O(log n) 次，每次验证需要 O(n) 时间。

相关题目