2064. 分配给商店的最多商品的最小值

🟠   🔖  数组 二分查找  🔗 力扣 LeetCode

题目

You are given an integer n indicating there are n specialty retail stores. There are m product types of varying amounts, which are given as a 0-indexed integer array quantities, where quantities[i] represents the number of products of the ith product type.

You need to distribute all products to the retail stores following these rules:

• A store can only be given at most one product type but can be given any amount of it.
• After distribution, each store will have been given some number of products (possibly 0). Let x represent the maximum number of products given to any store. You want x to be as small as possible, i.e., you want to minimize the maximum number of products that are given to any store.

Return the minimum possible x.

Example 1:

Input: n = 6, quantities = [11,6]

Output: 3

Explanation: One optimal way is:

• The 11 products of type 0 are distributed to the first four stores in these amounts: 2, 3, 3, 3
• The 6 products of type 1 are distributed to the other two stores in these amounts: 3, 3

The maximum number of products given to any store is max(2, 3, 3, 3, 3, 3) = 3.

Example 2:

Input: n = 7, quantities = [15,10,10]

Output: 5

Explanation: One optimal way is:

• The 15 products of type 0 are distributed to the first three stores in these amounts: 5, 5, 5
• The 10 products of type 1 are distributed to the next two stores in these amounts: 5, 5
• The 10 products of type 2 are distributed to the last two stores in these amounts: 5, 5

The maximum number of products given to any store is max(5, 5, 5, 5, 5, 5, 5) = 5.

Example 3:

Input: n = 1, quantities = [100000]

Output: 100000

Explanation: The only optimal way is:

• The 100000 products of type 0 are distributed to the only store.

The maximum number of products given to any store is max(100000) = 100000.

Constraints:

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

题目大意

给你一个整数 n ，表示有 n 间零售商店。总共有 m 种产品，每种产品的数目用一个下标从 0 开始的整数数组 quantities 表示，其中 quantities[i] 表示第 i 种商品的数目。

你需要将 所有商品 分配到零售商店，并遵守这些规则：

• 一间商店 至多 只能有 一种商品 ，但一间商店拥有的商品数目可以为 任意 件。
• 分配后，每间商店都会被分配一定数目的商品（可能为 0 件）。用 x 表示所有商店中分配商品数目的最大值，你希望 x 越小越好。也就是说，你想 最小化 分配给任意商店商品数目的 最大值 。

请你返回最小的可能的 x 。

示例 1：

输入： n = 6, quantities = [11,6]

输出： 3

解释： 一种最优方案为：

• 11 件种类为 0 的商品被分配到前 4 间商店，分配数目分别为：2，3，3，3 。
• 6 件种类为 1 的商品被分配到另外 2 间商店，分配数目分别为：3，3 。

分配给所有商店的最大商品数目为 max(2, 3, 3, 3, 3, 3) = 3 。

示例 2：

输入： n = 7, quantities = [15,10,10]

输出： 5

解释： 一种最优方案为：

• 15 件种类为 0 的商品被分配到前 3 间商店，分配数目为：5，5，5 。
• 10 件种类为 1 的商品被分配到接下来 2 间商店，数目为：5，5 。
• 10 件种类为 2 的商品被分配到最后 2 间商店，数目为：5，5 。

分配给所有商店的最大商品数目为 max(5, 5, 5, 5, 5, 5, 5) = 5 。

示例 3：

输入： n = 1, quantities = [100000]

输出： 100000

解释： 唯一一种最优方案为：

• 所有 100000 件商品 0 都分配到唯一的商店中。

分配给所有商店的最大商品数目为 max(100000) = 100000 。

提示：

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

解题思路

这个问题实际上是一个 二分查找 问题。

我们要找到最小的 num，使得所有产品都能分配到商店中，并且每个商店分配的产品数量不超过 num。

1. 对于产品 i，要分配 quantities[i] 个数目的产品，需要的最小商店数量是 ceil(quantities[i] / num)。

2. 可以通过二分查找来找到最小的合适的 num，二分查找的范围是：low = 1（每个商店至少需要 1 个产品），high = max(quantities)（每个商店最多能接受最大值的产品）。

3. 通过计算所有产品所需的总商店数量来判断是否满足 n 个商店的限制。

   • 如果所需商店数量大于 n，则说明 num 太小，需要增大它。
   • 如果所需商店数量小于或等于 n，则说明当前的 num 是有效的，尝试更小的 num。

4. 不断缩小二分查找的范围，直到 low == high，即最小化的最大产品数量。

复杂度分析

• 时间复杂度：O(n * log(Max(quantities))))，二分查找的范围是 [1, max(quantities)]，所以二分查找的时间复杂度为 O(log(Max(quantities)))，每次二分查找都需要遍历一次 quantities，其中 n 是数组 quantities 的长度，所以总的时间复杂度为 O(n * log(Max(quantities)))

• 空间复杂度：O(1)，只用了常数空间来存储一些辅助变量。

代码

/**
 * @param {number[]} quantities
 * @param {number} n
 * @return {number}
 */
var minimizedMaximum = function (quantities, n) {
	let low = 1,
		high = Math.max(...quantities);

	// 二分查找最小的最大产品数量
	while (low < high) {
		let mid = Math.floor((low + high) / 2);

		// 计算分配产品所需的商店数
		let storeCount = 0;
		for (let quantity of quantities) {
			storeCount += Math.ceil(quantity / mid); // 每个商店最多接受 mid 个产品
		}

		if (storeCount > n) {
			low = mid + 1; // 如果商店数超过 m，说明 mid 太小
		} else {
			high = mid; // 如果商店数不超过 m，尝试更小的 mid
		}
	}

	return low; // low 和 high 会最终相等，表示最小化的最大产品数量
};

相关题目

题号	标题	题解	标签	难度	力扣
875	爱吃香蕉的珂珂		数组 二分查找	🟠	🀄️ 🔗
1011	在 D 天内送达包裹的能力		数组 二分查找	🟠	🀄️ 🔗
1283	使结果不超过阈值的最小除数		数组 二分查找	🟠	🀄️ 🔗
1552	两球之间的磁力		数组 二分查找 排序	🟠	🀄️ 🔗
1760	袋子里最少数目的球		数组 二分查找	🟠	🀄️ 🔗
2187	完成旅途的最少时间		数组 二分查找	🟠	🀄️ 🔗
2226	每个小孩最多能分到多少糖果		数组 二分查找	🟠	🀄️ 🔗
2398	预算内的最多机器人数目		队列 数组 二分查找 4+	🔴	🀄️ 🔗