Medium

题目描述

给你一个整数 n ，表示有 n 家专门的零售商店。有 m 种不同数量的产品，用一个 0 下标 的整数数组 quantities 给出，其中 quantities[i] 表示第 i 种产品的数量。

你需要将所有产品分配给零售商店，需要遵循这些规则：

  • 一家商店 至多 只能分得 一种产品 ，但可以分得该种产品的 任意数量 。
  • 分配后，每家商店都会被分配一定数量的产品（可能为 0）。设 x 为分配给任意商店的最多产品数量，你希望 x 尽可能小。也就是说，你想 最小化 分配给任意商店的最多商品数量。

返回最小的可能的 x 。

示例 1：

输入：n = 6, quantities = [11,6]
输出：3
解释：一种最优分配方式如下：
- 类型为 0 的 11 件产品被分配到前 4 家商店，数量为：2, 3, 3, 3
- 类型为 1 的 6 件产品被分配到另外 2 家商店，数量为：3, 3
分配给任意商店的最多产品数量为 max(2, 3, 3, 3, 3, 3) = 3 。

示例 2：

输入：n = 7, quantities = [15,10,10]
输出：5
解释：一种最优分配方式如下：
- 类型为 0 的 15 件产品被分配到前 3 家商店，数量为：5, 5, 5
- 类型为 1 的 10 件产品被分配到接下来 2 家商店，数量为：5, 5  
- 类型为 2 的 10 件产品被分配到最后 2 家商店，数量为：5, 5
分配给任意商店的最多产品数量为 max(5, 5, 5, 5, 5, 5, 5) = 5 。

示例 3：

输入：n = 1, quantities = [100000]
输出：100000
解释：唯一最优分配方式如下：
- 类型为 0 的 100000 件产品被分配到唯一的商店。
分配给任意商店的最多产品数量为 max(100000) = 100000 。

提示：

  • m == quantities.length
  • 1 <= m <= n <= 10^5
  • 1 <= quantities[i] <= 10^5

解题思路

这是一道经典的二分查找 + 贪心问题。我们需要找到使得所有商品都能成功分配的最小的最大值。

核心思路

题目具有单调性：如果我们能以最大值 k 分配所有商品，那么对于任何 k' > k 也一定能成功分配。因此可以使用二分查找来寻找最小的可行 k。

算法步骤

  1. 确定二分查找的范围：

    • 下界：1（最少每家店分配1件商品）
    • 上界：max(quantities)（最坏情况下某类商品全部给一家店）

  2. 实现判断函数 canDistribute(k)：

    • 遍历每种商品类型
    • 对于数量为 q 的商品，如果每家店最多分配 k 件，需要 ceil(q/k) 家店
    • 所有商品类型需要的店铺总数不能超过 n

  3. 二分查找最小值：

    • 如果当前值 mid 可行，尝试更小的值（right = mid）
    • 如果不可行，必须增大值（left = mid + 1）

关键点

  • 使用 (q + k - 1) / k 计算向上取整，避免浮点运算
  • 贪心策略：每种商品尽可能平均分配给多家店铺
  • 时间复杂度：O(m * log(max_quantity))，其中 m 为商品种类数

代码实现

class Solution {
public:
    int minimizedMaximum(int n, vector<int>& quantities) {
        int left = 1, right = *max_element(quantities.begin(), quantities.end());
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canDistribute(n, quantities, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    
private:
    bool canDistribute(int n, vector<int>& quantities, int k) {
        int stores = 0;
        for (int q : quantities) {
            stores += (q + k - 1) / k;  // 向上取整
            if (stores > n) return false;
        }
        return true;
    }
};

class Solution:
    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:
        def canDistribute(k):
            stores = 0
            for q in quantities:
                stores += (q + k - 1) // k  # 向上取整
                if stores > n:
                    return False
            return True
        
        left, right = 1, max(quantities)
        while left < right:
            mid = (left + right) // 2
            if canDistribute(mid):
                right = mid
            else:
                left = mid + 1
        return left

public class Solution {
    public int MinimizedMaximum(int n, int[] quantities) {
        int left = 1, right = quantities.Max();
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (CanDistribute(n, quantities, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    
    private bool CanDistribute(int n, int[] quantities, int k) {
        int stores = 0;
        foreach (int q in quantities) {
            stores += (q + k - 1) / k;  // 向上取整
            if (stores > n) return false;
        }
        return true;
    }
}

var minimizedMaximum = function(n, quantities) {
    function canDistribute(k) {
        let stores = 0;
        for (let q of quantities) {
            stores += Math.ceil(q / k);
            if (stores > n) return false;
        }
        return true;
    }
    
    let left = 1, right = Math.max(...quantities);
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (canDistribute(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度时间复杂度空间复杂度
时间O(m × log(max_quantity))O(1)
空间O(1)O(1)

其中 m 是商品种类数，max_quantity 是商品数量的最大值。二分查找需要 log(max_quantity) 次迭代，每次迭代需要 O(m) 时间来检查是否可以分配。

相关题目