What is the primary pattern in the 'Minimum Limit of Balls in a Bag' problem?

The primary pattern is binary search over the valid answer space to minimize the maximum number of balls in any bag after performing splits.

How does binary search help in solving the problem?

Binary search helps by narrowing down the possible values of the maximum bag size, allowing you to efficiently find the minimal penalty after the splits.

What is the time complexity of the 'Minimum Limit of Balls in a Bag' problem?

The time complexity is O(n log k), where n is the number of bags and k is the maximum number of balls in a bag.

What happens if maxOperations is larger than the number of bags?

If maxOperations exceeds the number of bags, it may still not be enough to reduce the largest bag size to a smaller value, and you will need to use binary search to determine the smallest feasible maximum bag size.

What are common mistakes when solving this problem?

Common mistakes include misunderstanding the goal of minimizing the maximum bag size instead of the number of splits, and failing to properly calculate the number of splits required for each bag.

#1760

Medium

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

LeetCode 题解工作台

袋子里最少数目的球

给你一个整数数组 nums ，其中 nums[i] 表示第 i 个袋子里球的数目。同时给你一个整数 maxOperations 。你可以进行如下操作至多 maxOperations 次：选择任意一个袋子，并将袋子里的球分到 2 个新的袋子中，每个袋子里都有正整数个球。比方说，一个袋子里有 …

数组二分查找

题目描述

给你一个整数数组 nums ，其中 nums[i] 表示第 i 个袋子里球的数目。同时给你一个整数 maxOperations 。

你可以进行如下操作至多 maxOperations 次：

选择任意一个袋子，并将袋子里的球分到 2 个新的袋子中，每个袋子里都有 正整数 个球。
- 比方说，一个袋子里有 5 个球，你可以把它们分到两个新袋子里，分别有 1 个和 4 个球，或者分别有 2 个和 3 个球。

你的开销是单个袋子里球数目的 最大值 ，你想要 最小化 开销。

请你返回进行上述操作后的最小开销。

示例 1：

输入：nums = [9], maxOperations = 2
输出：3
解释：
- 将装有 9 个球的袋子分成装有 6 个和 3 个球的袋子。[9] -> [6,3] 。
- 将装有 6 个球的袋子分成装有 3 个和 3 个球的袋子。[6,3] -> [3,3,3] 。
装有最多球的袋子里装有 3 个球，所以开销为 3 并返回 3 。

示例 2：

输入：nums = [2,4,8,2], maxOperations = 4
输出：2
解释：
- 将装有 8 个球的袋子分成装有 4 个和 4 个球的袋子。[2,4,8,2] -> [2,4,4,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,4,4,4,2] -> [2,2,2,4,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,4,4,2] -> [2,2,2,2,2,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2] 。
装有最多球的袋子里装有 2 个球，所以开销为 2 并返回 2 。

示例 3：

输入：nums = [7,17], maxOperations = 2
输出：7

提示：

1 <= nums.length <= 10⁵
1 <= maxOperations, nums[i] <= 10⁹

lightbulb

解题思路

方法一：二分查找

本题需要我们最小化开销，即最小化单个袋子里球数目的最大值。随着最大值的增大，操作次数会减少，越容易满足条件。

因此，我们可以二分枚举单个袋子里球数目的最大值，判断是否能在 $\textit{maxOperations}$ 次操作内得到。

具体地，我们定义二分查找的左边界 $l = 1$ ，右边界 $r = \max(\textit{nums})$ 。然后我们不断二分枚举中间值 $\textit{mid} = \frac{l + r}{2}$ ，对于每个 $\textit{mid}$ ，我们计算在这个 $\textit{mid}$ 下，需要的操作次数。如果操作次数小于等于 $\textit{maxOperations}$ ，说明 $\textit{mid}$ 满足条件，我们将右边界 $r$ 更新为 $\textit{mid}$ ，否则将左边界 $l$ 更新为 $\textit{mid} + 1$ 。

最后，我们返回左边界 $l$ 即可。

时间复杂度 $O(n \times \log M)$ ，其中 $n$ 和 $M$ 分别是数组 $\textit{nums}$ 的长度和最大值。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

class Solution:
    def minimumSize(self, nums: List[int], maxOperations: int) -> int:
        def check(mx: int) -> bool:
            return sum((x - 1) // mx for x in nums) <= maxOperations

        return bisect_left(range(1, max(nums) + 1), True, key=check) + 1

speed

复杂度分析

指标	值
时间	O(n \log k)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
The candidate understands how to apply binary search to a problem involving finding an optimal solution in a range.
question_mark
The candidate demonstrates understanding of problem constraints and how to balance performance and correctness in large inputs.
question_mark
The candidate effectively uses the binary search technique to narrow down the feasible solution space and optimize the answer.

warning

常见陷阱

外企场景

error
Forgetting to check if the candidate maximum bag size can be achieved with the given maxOperations.
error
Misinterpreting the problem as needing to minimize the number of splits, rather than the maximum bag size after splitting.
error
Incorrectly handling edge cases such as very small or very large values in the nums array or maxOperations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if there were additional constraints such as only being able to split bags in a certain ratio?
arrow_right_alt
How would the solution change if the number of splits were unlimited, and you needed to minimize the largest bag size?
arrow_right_alt
What if there were a constraint that you could only split bags evenly or into specific sizes?

help

常见问题

外企场景

继续练习

#1751 最多可以参加的会议数目 II #1782 统计点对的数目 #1793 好子数组的最大分数