⚡Flashcard Drill➔
NeetCode #281LC-2064MediumBinary Search
← Back to All Problems

#281 · #2064 · Minimized Maximum of Products Distributed to Any Store(分配给商店的最多商品的最小值)

📌 Problem Statement & Constraints

You are given n stores and an array quantities where quantities[i] is the number of products of type i. You must distribute all products to the stores, and each store receives products of only one type. Return the minimum possible maximum number of products given to any store. Constraints: 1 <= n <= 10^5, 1 <= m <= 10^5, 1 <= quantities[i] <= 10^5.

💡 Core Algorithmic Approaches

  1. Binary search on the answer x: "can every store receive at most x products" is monotone in x.
  2. For a given x, the number of stores needed for type i is ceil(quantities[i] / x), so the total is sum(ceil(q / x)).
  3. The answer is feasible when the total is at most n. Use hi = mid to find the smallest feasible x.
  4. The lower bound is 1 and the upper bound is max(quantities), since one store can always take a whole type.

💻 Benchmark Python3 Implementation

class Solution:
    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:
        lo, hi = 1, max(quantities)
        while lo < hi:
            mid = (lo + hi) // 2
            # stores needed if each store takes at most mid products
            stores = sum((q + mid - 1) // mid for q in quantities)
            if stores <= n:
                hi = mid               # feasible -> try a smaller cap
            else:
                lo = mid + 1
        return lo

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m log(max(quantities))): each feasibility check is O(m).
💾 Space Complexity
O(1): a few scalars.

⚠️ Interview Pitfalls & Follow-ups

  • Using q // mid instead of the ceiling: integer division truncates, so the store count would be underestimated.
  • Using hi = mid - 1 when feasible: could skip the optimum.
  • Assuming products can be split across stores: each store receives only one type, which is why the ceiling division is per type.
  • Setting the lower bound to 0: a cap of 0 is infeasible whenever any quantity is positive.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Binary Search Problems

中文速览与面试要点

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

给你一个整数 n,表示有 n 间零售商店。总共有 m 种产品,每种产品的数目用一个下标从 0 开始的整数数组 quantities 表示,其中 quantities[i] 表示第 i 种商品的数目。你需要将 所有商品 分配到零售商店,并遵守这些规则:① 一间商店 至多 分配一种商品;② 分配后,每间商店都会被分配一定数目的商品(可以为 0);③ 任意一种商品都可以分配给任意数目的商店。请你返回 最多 分配到商品的商店数目的 最小值 。约束:1 ≤ n ≤ 10^5;1 ≤ m ≤ 10^5;1 ≤ quantities[i] ≤ 10^5。

核心要点

  • 二分答案(标准解) :二分「每间商店分配的商品数上限 x」,判定「所有商品能否在 n 间商店内分配完」。
  • 单调性 :x 越大,所需商店数越少,因此可以二分(求最小值)。
  • 判定函数 :第 i 种商品需要 ceil(quantities[i] / x) 间商店,总需求为 Σ ceil(q / x) ,判断是否 ≤ n。
  • 为什么一间商店最多一种商品使问题简化 :每种商品独立计算所需商店数,互不影响,因此可以直接求和。

常见陷阱

  • 用浮点除法后取整 : math.ceil(q / x) 有精度风险。用整数向上取整 (q + x − 1) // x 。
  • 上界写成 sum(quantities) :二分次数变多;上界取 max(quantities) 更紧且正确(每种商品至少占一间商店时上限就是它的数量)。
  • 判定条件写成 == n :所需商店数可能少于 n(多余的商店分 0 个商品),应判断 &lt;= n 。
  • 下界写成 0 :会除零。下界应为 1。

参考实现

class Solution:
    def minimizedMaximum(self, n: int, quantities: list[int]) -> int:
        def stores_needed(x: int) -> int:
            # 每种商品需要 ceil(q / x) 间商店
            return sum((q + x - 1) // x for q in quantities)

        l, r = 1, max(quantities)
        while l < r:
            mid = (l + r) // 2
            if stores_needed(mid) <= n:
                r = mid                 # 可行 -> 尝试更小的上限
            else:
                l = mid + 1
        return l