What is the main idea behind minimizing the maximum products per store?

Use binary search over possible maximums and a greedy approach to check if distribution is feasible for each candidate.

Why does binary search work in this problem?

Because the feasibility of a maximum x is monotonic: if x is too small, it fails; any larger x will succeed.

How do I compute required stores for each product type?

Divide the quantity of each type by the candidate maximum x, rounding up to get the number of stores needed.

Can GhostInterview suggest the actual allocation per store?

It focuses on the minimized maximum value, but the greedy checks also outline how products could be distributed.

Does this problem pattern relate to other binary search over answer problems?

Yes, it exemplifies the 'Binary search over the valid answer space' pattern common in allocation and capacity optimization problems.

#2064

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

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

给你一个整数 n ，表示有 n 间零售商店。总共有 m 种商品，每种商品的数目用一个下标从 0 开始的整数数组 quantities 表示，其中 quantities[i] 表示第 i 种商品的数目。你需要将所有商品分配到零售商店，并遵守这些规则：一间商店至多只能有一种商品，但一间商…

数组二分查找贪心

题目描述

给你一个整数 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⁵
1 <= quantities[i] <= 10⁵

lightbulb

解题思路

方法一：二分查找

我们注意到，如果分配给任意商店商品数目的最大值为 $x$ ，且满足题目要求，那么 $x+1$ 也一定满足题目要求，这存在着单调性。因此我们可以通过二分查找，找到一个最小的 $x$ ，使得 $x$ 满足题目要求。

我们定义二分查找的左边界 $left=1$ ，右边界 $right=10^5$ 。对于二分查找的每一步，我们取中间值 $mid$ ，判断是否存在一个分配方案，使得分配给任意商店商品数目的最大值为 $mid$ ，如果存在，那么我们将右边界 $right$ 移动到 $mid$ ，否则将左边界 $left$ 移动到 $mid+1$ 。

二分查找结束后，答案即为 $left$ 。

时间复杂度 $O(m \times \log M)$ ，空间复杂度 $O(1)$ 。其中 $m$ 为商品种类数，而 $M$ 为商品数目的最大值，本题中 $M \leq 10^5$ 。

1

2

3

4

5

6

7

class Solution:
    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:
        def check(x):
            return sum((v + x - 1) // x for v in quantities) <= n

        return 1 + bisect_left(range(1, 10**6), True, key=check)

speed

复杂度分析

指标	值
时间	complexity is O(m log(maxQuantity)) due to binary search over possible maximums and O(m) check per candidate. Space complexity is O(m) for storing quantities and temporary calculations.
空间	O(m)

psychology

面试官常问的追问

外企场景

question_mark
Look for efficient allocation instead of simulating all permutations.
question_mark
Consider the monotonic behavior when maximum per store changes.
question_mark
Expect binary search over the answer rather than direct computation.

warning

常见陷阱

外企场景

error
Trying to distribute products sequentially without bounding the maximum.
error
Not accounting for the required number of stores per product type.
error
Confusing the maximum per store with average allocation.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Change the problem to minimize the sum of squares of products per store.
arrow_right_alt
Limit each store to at most k types of products and find the minimized maximum.
arrow_right_alt
Allow splitting products partially, requiring fractional distribution calculations.

help

常见问题

外企场景

继续练习

#2071 你可以安排的最多任务数目 #2141 同时运行 N 台电脑的最长时间 #2234 花园的最大总美丽值