本质是二分答案求最小。二分的 mid 表示上界。

1. 410. 分割数组的最大值

   class Solution:
   def splitArray(self, nums: List[int], k: int) -> int:
   
       # 根据当前子数组最大值，返回子数组的个数
       def check(nums, mid):
           temp = 0
           res = 1
           for num in nums:
               temp += num
               if temp <= mid:
                   continue
               res += 1
               temp = num
           return res
   
       left = max(nums) - 1 # k = len(nums)
       right = sum(nums) + 1 # k = 1
       while left + 1 < right:
           mid = (left + right) // 2
           if check(nums, mid) <= k: # k变大输出会变小，因此 check 小于 k 时，想让 k 变大 mid 要变小
               right = mid
           else:
               left = mid
       return right

   时间复杂度：O(nlogU)，其中 n 是 candies 的长度，U 为 sum(nums) - max(nums)。

   空间复杂度：O(1)

2. 2064. 分配给商店的最多商品的最小值

   class Solution:
   def minimizedMaximum(self, n: int, quantities: List[int]) -> int:
   
       def divide_up(x, l):
           if x // l == x / l:
               return x // l
           else:
               return x // l + 1
   
       left = 0
       right = max(quantities)
       while left + 1 < right:
           mid = (left + right) // 2
           if sum(divide_up(q, mid) for q in quantities) <= n:
               right = mid
           else:
               left = mid
       return right

   时间复杂度：O(nlogU)，其中 n 是 quantities 的长度，U 为 max(quantities)。

   空间复杂度：O(1)

3. 1760. 袋子里最少数目的球

   主打一个代码又臭又长，没有技巧，全是模拟

   class Solution:
   def minimumSize(self, nums: List[int], maxOperations: int) -> int:
   
       def help(x, l):
           """
           返回x分成一个个不超过l的数需要的次数
           >>>help(9, 2)
           >>>4
           >>>help(8, 2)
           >>>3
           """
           if x // l == x / l:
               return x // l - 1
           else:
               return x // l
   
       def check(nums, mid):
           res = 0
           for num in nums:
               if num > mid:
                   res += help(num, mid)
                   if res > maxOperations:
                       return False
           return True
   
       left = 0
       right = max(nums)
       while left + 1 < right:
           mid = (left + right) // 2
           if check(nums, mid):
               right = mid
           else:
               left = mid
       return right

   时间复杂度：O(nlogU)，其中 n 是 nums 的长度，U 为 max(nums)。

   空间复杂度：O(1)