Medium

题目描述

给你一个下标从 0 开始的整数数组 candies。数组中的每个元素表示大小为 candies[i] 的一堆糖果。你可以将每堆糖果分成任意数量的子堆，但 不能 将两堆糖果合并在一起。

同时给你一个整数 k。你需要将这些糖果堆分配给 k 个孩子，使得每个孩子都能获得 相同数量 的糖果。每个孩子可以分配到的糖果都来自于同一堆，并且有些糖果堆可能不会被使用。

返回每个孩子可以获得的 最大糖果数目 。

示例 1：

输入：candies = [5,8,6], k = 3
输出：5
解释：我们可以将 candies[1] 分成大小为 5 和 3 的两堆，将 candies[2] 分成大小为 5 和 1 的两堆。现在我们有五堆糖果，大小分别为 5、5、3、5 和 1 。我们可以把 3 堆大小为 5 的糖果分配给 3 个孩子。可以证明每个孩子无法获得超过 5 颗糖果。

示例 2：

输入：candies = [2,5], k = 11
输出：0
解释：总共有 11 个孩子，但只有 7 颗糖果，所以不可能保证每个孩子至少能获得一颗糖果。因此，每个孩子都得不到糖果，答案是 0 。

提示：

  • 1 <= candies.length <= 10^5
  • 1 <= candies[i] <= 10^7
  • 1 <= k <= 10^12

解题思路

这是一个典型的二分搜索问题。关键在于理解题目要求：我们需要找到每个孩子能获得的最大糖果数量。

核心思路：

对于给定的糖果数量 x，我们可以检查是否能让 k 个孩子每人都获得 x 颗糖果：

  • 遍历每堆糖果，计算每堆能提供多少个大小为 x 的子堆（即 candies[i] / x）
  • 如果总的子堆数量 ≥ k，则可以满足要求

二分搜索策略：

  • 左边界：0（最坏情况下每个孩子得不到任何糖果）
  • 右边界：糖果总数 / k（理论最大值）
  • 对于中间值 mid，检查是否可行：
    • 如果可行，说明答案可能更大，在右半部分继续搜索
    • 如果不可行，说明 mid 太大，在左半部分搜索

这种方法的时间复杂度为 O(n × log(sum/k))，其中 n 是糖果堆的数量。空间复杂度为 O(1)。

推荐解法： 二分搜索是最优解法，既高效又容易理解。

代码实现

class Solution {
public:
    int maximumCandies(vector<int>& candies, long long k) {
        long long sum = 0;
        for (int candy : candies) {
            sum += candy;
        }
        
        long long left = 0, right = sum / k;
        
        while (left < right) {
            long long mid = left + (right - left + 1) / 2;
            
            long long count = 0;
            for (int candy : candies) {
                count += candy / mid;
            }
            
            if (count >= k) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        
        return left;
    }
};

class Solution:
    def maximumCandies(self, candies: List[int], k: int) -> int:
        left, right = 0, sum(candies) // k
        
        while left < right:
            mid = (left + right + 1) // 2
            
            count = sum(candy // mid for candy in candies)
            
            if count >= k:
                left = mid
            else:
                right = mid - 1
        
        return left

public class Solution {
    public int MaximumCandies(int[] candies, long k) {
        long sum = 0;
        foreach (int candy in candies) {
            sum += candy;
        }
        
        long left = 0, right = sum / k;
        
        while (left < right) {
            long mid = left + (right - left + 1) / 2;
            
            long count = 0;
            foreach (int candy in candies) {
                count += candy / mid;
            }
            
            if (count >= k) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        
        return (int)left;
    }
}

var maximumCandies = function(candies, k) {
    const sum = candies.reduce((acc, candy) => acc + candy, 0);
    let left = 0, right = Math.floor(sum / k);
    
    while (left < right) {
        const mid = Math.floor((left + right + 1) / 2);
        
        let count = 0;
        for (const candy of candies) {
            count += Math.floor(candy / mid);
        }
        
        if (count >= k) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    
    return left;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n × log(sum/k))n 为糖果堆数量，二分搜索范围为 [0, sum/k]，每次检查需要遍历所有糖果堆
空间复杂度O(1)只使用常数额外空间

相关题目