难度: Hard
Submission
运行时间: 75 ms
内存: 17.0 MB
class Solution:
def maximizeSweetness(self, sweetness: List[int], k: int) -> int:
left = min(sweetness)
right = sum(sweetness) // (k + 1)
while left < right:
tmp_sum = 0
p = 0
mid = (left + right +1) // 2
for sw in sweetness:
tmp_sum += sw
if tmp_sum >= mid:
tmp_sum = 0
p += 1
if p >= k + 1:
left = mid
else:
right = mid - 1
return right
Explain
本题的思路基于二分搜索。目标是找到最大的最小巧克力量，使得可以至少分成k+1份，每份的巧克力量至少是这个最小值。我们通过设置搜索范围left和right，left是单块巧克力的最小值，right是所有巧克力总量除以k+1的结果。通过二分搜索，逐渐缩小这个范围来找到最大的最小值。在每一步的二分搜索中，我们检查能否生成至少k+1块巧克力，每块至少有mid的甜度。如果可以，我们尝试一个更大的最小值（增加left），否则减小这个值（减小right）。重复这个过程直到left和right相遇，此时的right即为所求。
时间复杂度: O(n log(sum(sweetness) / (k + 1)))
空间复杂度: O(1)
class Solution:
def maximizeSweetness(self, sweetness: List[int], k: int) -> int:
left = min(sweetness) # 最小单块甜度
right = sum(sweetness) // (k + 1) # 最大可能的最小甜度
while left < right:
tmp_sum = 0 # 当前分块的甜度总和
p = 0 # 分成的块数
mid = (left + right +1) // 2 # 当前尝试的最小甜度值
for sw in sweetness:
tmp_sum += sw
if tmp_sum >= mid: # 如果当前块的甜度达到了mid，重新开始计数
tmp_sum = 0
p += 1
if p >= k + 1: # 如果可以分成超过k+1块，尝试更大的甜度值
left = mid
else: # 否则尝试更小的甜度值
right = mid - 1
return right # 最终的最大最小甜度值
Explore
右边界right被设置为所有巧克力总量除以k+1，是因为我们需要找到最大的最小甜度值，使得可以至少分成k+1份。如果我们将每一份的甜度设为总甜度除以k+1，那么这是在理想情况下每一份可以达到的最大甜度值。设置这个值为right的初始值，是因为任何大于这个值的甜度都不可能实现至少k+1份的要求，因此这个值是搜索的一个合理上界。
在二分搜索中使用`(left + right + 1) // 2`作为mid的计算方式主要是为了确保在left与right非常接近时，mid能够适当地偏向right，从而避免在某些情况下进入死循环。特别是当left和right相差1时，使用`(left + right) // 2`可能会导致mid重复地等于left，从而使得搜索陷入无法前进的状态。使用`(left + right + 1) // 2`则可以确保mid在数值上能够向right逼近，有助于搜索过程的顺利进行。
将tmp_sum重置为0的原因在于我们需要开始计算新的一块巧克力块，以确保每块都至少有mid的甜度。这种做法并不会导致巧克力的浪费，而是为了确保每一块巧克力的甜度都符合题目要求的最小甜度mid。如果不重置tmp_sum，那么累积的甜度会超过mid，这可能导致无法达到至少k+1块的条件，因为超出的甜度可能会使得其中一些块的甜度不足。因此，每当一块巧克力的甜度达到了mid，我们就完成了对这一块的计算，并开始为下一块计算，确保所有块都能公平地分配甜度。