二分算法 （二）

题目总览

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

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

二分作为中间手段

3143.正方形中的最多点数

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

最大化最小值

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

题目详解

3143.正方形中的最多点数

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

class Solution:
    def maxPointsInsideSquare(self, points: List[List[int]], s: str) -> int:
        ans = 0
        def 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 False
                    vis.add(c)
            nonlocal ans 
            ans = len(vis)
            return True
        left ,right = 0,1000_000_000
        while left<=right:
            mid = (left+right)//2
            # 满足条件
            if check(mid):
                left=mid+1
            else:
                right=mid-1
        return ans
            


        

410.分割数组的最大值

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

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

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        ans = 0
        def check(mid):
            numk , s = 1,0
            for i in nums:
                if s + i <= mid:
                    s += i
                else:
                    # 新开一段
                    numk+=1
                    s = i 
                    if numk>k:
                        return False

            nonlocal ans
            ans = mid
            return True
        
        left,right = max(nums),sum(nums)
        # 单调性的体现，对于最大值的最小，当你划分的k越小，则越大
        while left<=right:
            mid = (left+right)//2
            # 如果满足条件，则可以变小看看
            if check(mid):
                right=mid -1
            else:
                left=mid +1
        return 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 False
            return True
        left,right = 0, 2000_000_001
        # 贪心思想，如果此时的mid满足，表示至少可以满足
        while left<=right:
            mid = (left+right)//2
            if check(mid):
                left=mid+1
            else:
                right=mid-1
        return right