2.2.1 求最小

提示

阿囧说：如果答案有单调性，那么可以二分答案。这种类型的题，要找好二分的左右端点，左右端点一般是可以继续优化的，从而降低时间复杂度

1. 1283. 使结果不超过阈值的最小除数

   我最初的写法过了 70/71 个样例，最后一个过不了，太抽象了

   class Solution:
   def smallestDivisor(self, nums: List[int], threshold: int) -> int:
   
       def division_up(x, l):
           if x // l == x / l:
               return x // l
           else:
               return x // l + 1
   
       left = 0
       right = max(nums)
       while left + 1 < right:
           mid = (left + right) // 2
           if sum(division_up(num, mid) for num in nums) <= threshold:
               right = mid
           else:
               left = mid
       return right

   时间复杂度：O(nlogU)，其中 n 是 nums 的长度，U=max(nums)。二分 O(logU) 次，每次 O(n) 遍历 nums。

   空间复杂度：O(1)

2. 2187. 完成旅途的最少时间

   class Solution:
   def minimumTime(self, time: List[int], totalTrips: int) -> int:
       left = 0
       right = min(time) * totalTrips
       while left + 1 < right:
           mid = (left + right) // 2
           if sum(mid // t for t in time) < totalTrips:
               left = mid
           else:
               right = mid
       return right

   时间复杂度：O(nlogU)，其中 n 为 time 的长度，U 为二分上下界之差。在本题数据范围下，U 不会超过 $10^{14}$

   空间复杂度：O(1)

3. 1870. 准时到达的列车最小时速

   class Solution:
   def minSpeedOnTime(self, dist: List[int], hour: float) -> int:
       if len(dist) >= hour + 1:
           return -1
   
       def division_up(x, l):
           if x // l == x / l:
               return x // l
           else:
               return x // l + 1
   
       left = 0
       right = max(dist) * 100
       while left + 1 < right:
           mid = (left + right) // 2
           if sum(division_up(d, mid) for d in dist[:-1]) + dist[-1] / mid <= hour:
               right = mid
           else:
               left = mid
       return right

   时间复杂度：O(nlogU)，其中 n 是 dist 的长度，U 为二分上下界之差。在本题数据范围下，U 不会超过 $10^7$

   空间复杂度：O(1)

4. 1011. 在 D 天内送达包裹的能力

   很明显，这种题型的 check 函数很好写，只要不断优化 left 和 right 就能过了

   class Solution:
   def shipWithinDays(self, weights: List[int], days: int) -> int:
   
       def check(weights, min_weights):
           now = 0
           res = 0
           for w in weights:
               now += w
               if now < min_weights:
                   continue
               res += 1
               now = w
           return res
   
       left = max(weights)
       right = sum(weights) + 1
       while left + 1 < right:
           mid = (left + right) // 2
           if check(weights, mid) < days:
               right = mid
           else:
               left = mid
       return left

   时间复杂度：O(nlogU)，其中 n 是 weights 的长度，U 为二分上下界之差。

   空间复杂度：O(1)

5. 875. 爱吃香蕉的珂珂

   class Solution:
   def minEatingSpeed(self, piles: List[int], h: int) -> int:
   
       def division_up(x, l):
           if x // l == x / l:
               return x // l
           else:
               return x // l + 1
   
       left = 0
       right = max(piles)
       while left + 1 < right:
           mid = (left + right) // 2
           if sum(division_up(p, mid) for p in piles) <= h:
               right = mid
           else:
               left = mid
       return right

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

   空间复杂度：O(1)

2.2.2 求最大

提示

灵神：在练习时，请注意「求最小」和「求最大」的二分写法上的区别。

前面的「求最小」和二分查找求「排序数组中某元素的第一个位置」是类似的，按照红蓝染色法，左边是不满足要求的（红色），右边则是满足要求的（蓝色）。

「求最大」的题目则相反，左边是满足要求的（蓝色），右边是不满足要求的（红色）。这会导致二分写法和上面的「求最小」有一些区别。

以开区间二分为例：

• 求最小：check(mid) == true 时更新 right = mid，反之更新 left = mid，最后返回 right。
• 求最大：check(mid) == true 时更新 left = mid，反之更新 right = mid，最后返回 left。

对于开区间写法，简单来说 check(mid) == true 时更新的是谁，最后就返回谁。相比其他二分写法，开区间写法不需要思考加一减一等细节，个人推荐使用开区间写二分。

sas sas

1. 275. H 指数 II

   最初的想法没有利用 citations 已经是有序的性质，check函数的时间复杂度是O(n)，导致最终是O(nlogn)，居然也能过

   class Solution:
   def hIndex(self, citations: List[int]) -> int:
   
       def check(citations, mid):
           res = 0
           for c in citations:
               if c >= mid:
                   res += 1
           return True if res >= mid else False
   
       left = -1
       right = len(citations) + 1
       while left + 1 < right:
           mid = (left + right) // 2
           if check(citations, mid):
               left = mid
           else:
               right = mid    
       return left

   时间复杂度：O(nlogn)，其中 n 是 citations 的长度。

   空间复杂度：O(1)

   利用 citations 有序

   class Solution:
   def hIndex(self, citations: List[int]) -> int:
       left = -1
       right = len(citations) + 1
       while left + 1 < right:
           mid = (left + right) // 2
           if citations[-mid] >= mid:
               left = mid
           else:
               right = mid    
       return left

   时间复杂度：O(logn)，其中 n 是 citations 的长度。

   空间复杂度：O(1)

2. 2226. 每个小孩最多能分到多少糖果

   class Solution:
   def maximumCandies(self, candies: List[int], k: int) -> int:
       left = 0
       right = max(candies) + 1
       while left + 1 < right:
           mid = (left + right) // 2
           if sum(c // mid for c in candies) < k:
               right = mid
           else:
               left = mid
       return left

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

   空间复杂度：O(1)