提示

二分的不是答案，而是一个和答案有关的值（间接值）。

1. 3143. 正方形中的最多点数

   我是究极无敌模拟怪

   class Solution:
   def maxPointsInsideSquare(self, points: List[List[int]], s: str) -> int:
       # 二分正方形的边长，先定义二分的左右边界
       left = -1
       new_points = []
       for p in points: # 将二维列表转化为一维列表
           new_points.append(max(abs(p[0]), abs(p[1])))
       right = max(new_points) + 1
   
       # 符合题意的 check 函数：超过两个相同的字母返回 False
       def check(new_points, mid):
           cnt = Counter()
           for i, n in enumerate(new_points):
               if n <= mid:
                   cnt[s[i]] += 1
                   if cnt[s[i]] == 2:
                       return False
           return True
   
       # 二分得到符合 check 的最大边长
       while left + 1 < right:
           mid = (left + right) // 2
           if check(new_points, mid):
               left = mid
           else:
               right = mid
   
       # 通过最大边长计算包含的点数 res
       res = 0
       for n in new_points:
           if n <= left:
               res += 1
       return res

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

   空间复杂度：O(n)