Medium

题目描述

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

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

  • 选择任意一个装有球的袋子，将它分成两个新的非空袋子。
  • 例如，一个装有 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。

提示：

  • 1 <= nums.length <= 10^5
  • 1 <= maxOperations, nums[i] <= 10^9

解题思路

这道题的核心思想是使用二分搜索来寻找最小的开销（即最大袋子的球数）。

解题思路：

  1. 转换问题角度：与其直接考虑如何分割，不如考虑给定一个目标开销值，我们需要多少次操作才能达到这个目标。

  2. 二分搜索的可行性：随着目标开销值的增大，需要的操作次数会减少，这是一个单调性关系，符合二分搜索的条件。

  3. 搜索范围：

    • 下界：1（每个袋子至少有1个球）
    • 上界：数组中的最大值（不进行任何操作时的开销）

  4. 验证函数：对于给定的目标开销 mid，计算需要的最小操作次数：

    • 对于每个袋子，如果球数超过 mid，需要分割成若干个不超过 mid 的袋子
    • 若袋子有 x 个球，目标开销是 mid，则需要的袋子数是 ceil(x/mid) = (x-1)/mid + 1
    • 因此需要的操作次数是 (x-1)/mid

  5. 二分逻辑：如果当前 mid 需要的操作次数不超过 maxOperations，说明可以达到更小的开销，继续在左半部分搜索；否则在右半部分搜索。

代码实现

class Solution {
public:
    int minimumSize(vector<int>& nums, int maxOperations) {
        int left = 1, right = *max_element(nums.begin(), nums.end());
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            long long operations = 0;
            
            for (int num : nums) {
                operations += (num - 1) / mid;
            }
            
            if (operations <= maxOperations) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
};

class Solution:
    def minimumSize(self, nums: List[int], maxOperations: int) -> int:
        left, right = 1, max(nums)
        
        while left < right:
            mid = (left + right) // 2
            operations = sum((num - 1) // mid for num in nums)
            
            if operations <= maxOperations:
                right = mid
            else:
                left = mid + 1
                
        return left

public class Solution {
    public int MinimumSize(int[] nums, int maxOperations) {
        int left = 1, right = nums.Max();
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            long operations = 0;
            
            foreach (int num in nums) {
                operations += (num - 1) / mid;
            }
            
            if (operations <= maxOperations) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
}

var minimumSize = function(nums, maxOperations) {
    let left = 1, right = Math.max(...nums);
    
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        let operations = 0;
        
        for (let num of nums) {
            operations += Math.floor((num - 1) / mid);
        }
        
        if (operations <= maxOperations) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log m)n 是数组长度，m 是数组最大值。二分搜索需要 log m 次，每次验证需要 O(n)
空间复杂度O(1)只使用常数额外空间

相关题目