二分算法 （二）

题目总览

二分作为求解答案的一种中间手段
关键在于这个check函数的定义，其中的话，大多数使用到贪心，因为是二分，会一步步接近这个结果，所以开始的范围大一点没有关系

最小化最大值和最大化最小值，首先想到这个二分算法

二分作为中间手段

3143.正方形中的最多点数

最小化最大值
410.分割数组的最大值

最大化最小值

3281.范围内整数的最大得分

题目详解

3143.正方形中的最多点数

思路分析：可以看到边长的范围很长，所以使用暴力是不可能在规定时间内求解的，由于边长的变化可以单调，所以我们可以以边长为变量进行使用二分求解，对于每一次得到的mid,我们再逐一判断是否有重复的元素(使用集合进行判断)

class Solution:def maxPointsInsideSquare(self, points: List[List[int]], s: str) -> int:ans = 0def check(mid):vis = set()for (x,y),c in zip(points,s):if abs(x) <= mid and abs(y) <= mid:if c in vis:return Falsevis.add(c)nonlocal ans ans = len(vis)return Trueleft ,right = 0,1000_000_000while left<=right:mid = (left+right)//2# 满足条件if check(mid):left=mid+1else:right=mid-1return ans

410.分割数组的最大值

思路分析：根据灵神的思路，

难点还是在于如何统计这个段数，其实只要我们从左往右，根据你传入的这个mid的值，根据是否能够累加得到，如果超过这个mid 值，则多开一段
当然，我们求解的是 这个最小的最大值，那我们就可以以这个为变量进行二分求解

class Solution:def splitArray(self, nums: List[int], k: int) -> int:ans = 0def check(mid):numk , s = 1,0for i in nums:if s + i <= mid:s += ielse:# 新开一段numk+=1s = i if numk>k:return Falsenonlocal ansans = midreturn Trueleft,right = max(nums),sum(nums)# 单调性的体现，对于最大值的最小，当你划分的k越小，则越大while left<=right:mid = (left+right)//2# 如果满足条件，则可以变小看看if check(mid):right=mid -1else:left=mid +1return left

3281.范围内整数的最大得分

思路分析：关键点还是在于check函数的定义，在这里是判断是否满足对于选择的数字是否满足这个区间的要求

class Solution:def maxPossibleScore(self, start: List[int], d: int) -> int:# 先按照升序排序start.sort()# check函数是使用贪心策略来构建的def check(mid):s = start[0]for i in range(1,len(start)):# if start[i] <= s + mid and s+mid <= start[i]+d:# 这个s+mid 不一定大于start[i]if s+mid <= start[i]+d:s = max(start[i],s +mid)else:return Falsereturn Trueleft,right = 0, 2000_000_001# 贪心思想，如果此时的mid满足，表示至少可以满足while left<=right:mid = (left+right)//2if check(mid):left=mid+1else:right=mid-1return right