求包含给定点且不与其他正方形相交的最大正方形边长

首先做前置校验：如果指定点(i,j)落在集合L的任意正方形内部，直接返回0，不存在符合要求的正方形。

核心优化思路：二分答案+定向相交检查 #

暴力枚举边长效率低的核心原因是做了大量冗余校验：边长的合法性是严格单调的——如果边长为s的正方形存在合法解，那么所有小于s的边长一定存在合法解，因此完全不需要从小到大逐一枚举，用二分法把边长枚举的次数从O(n)压缩到O(log n)即可，n取1e9的场景下也只需要30次左右的校验轮次。

二分校验逻辑 #

对于二分到的候选边长s，首先计算理论边界：

• 要让边长为s的正方形完全落在n×n网格内且包含(i,j)，正方形左上角(top, left)的取值范围是固定的：
  • top ∈ [t_min, t_max]，其中t_min = max(0, i - s + 1)，t_max = min(i, n - s)
  • left ∈ [l_min, l_max]，其中l_min = max(0, j - s + 1)，l_max = min(j, n - s)
• 如果t_min > t_max或l_min > l_max，说明当前s超出网格边界限制，直接判定不合法。
  接下来只需要判断：上述左上角取值范围内，是否存在一个点(top, left)，使得对应的正方形[top, top+s) × [left, left+s)不与L中任意正方形相交。

校验过程的性能优化 #

不需要每次校验都遍历L中所有正方形：

1. 范围过滤：只有落在[i-s, i+s] × [j-s, j+s]区域内的障碍物，才可能和当前候选边长的正方形相交，距离更远的障碍物完全不会产生交集，可以直接跳过。如果提前把L中正方形按坐标排序建索引（比如按x、y坐标排序的有序列表），每次可以用二分查找快速筛出候选障碍物，s较小时需要检查的障碍物数量极少。
2. 快速判定合法点：收集所有候选障碍物对top取值的切割点（障碍物上边界、下边界对应到top的限制位置），只需要遍历这些有限的切割点作为top的候选值，对每个top快速计算left的合法区间即可，不需要枚举所有可能的top和left。

实现参考（易上手通用版本） #

如果L的规模在1e5以内，完全不需要建复杂的空间索引，直接遍历所有障碍物做相交判定即可，30次轮次总操作量仅3e6，毫秒级就能跑完，代码容错率极高：

def max_square_side(n, L, i, j):
    # 预处理障碍物为x1,y1,x2,y2格式
    obs = []
    point_blocked = False
    for (x, y, s) in L:
        x2 = x + s
        y2 = y + s
        obs.append((x, y, x2, y2))
        # 顺便检查目标点是否被障碍物挡住
        if x <= i < x2 and y <= j < y2:
            point_blocked = True
    if point_blocked:
        return 0

    # 二分边界
    low = 1
    high = min(i+1, n - i, j+1, n - j)
    ans = 0

    def is_valid(s):
        t_min = max(0, i - s + 1)
        t_max = min(i, n - s)
        l_min = max(0, j - s + 1)
        l_max = min(j, n - s)
        if t_min > t_max or l_min > l_max:
            return False
        
        # 收集所有top的候选切割点
        t_candidates = {t_min, t_max}
        for (ox1, oy1, ox2, oy2) in obs:
            t_candidates.add(ox1 - s)
            t_candidates.add(ox2)
        # 只检查落在合法范围内的top
        check_ts = [t for t in t_candidates if t_min <= t <= t_max]

        for t in check_ts:
            cur_l_low = l_min
            cur_l_high = l_max
            square_x2 = t + s
            for (ox1, oy1, ox2, oy2) in obs:
                # x方向不相交，直接跳过
                if square_x2 <= ox1 or t >= ox2:
                    continue
                # x方向相交，计算y方向禁止的left区间
                forbid_l = oy1 - s + 1
                forbid_r = oy2 - 1
                # 无重叠，不影响
                if forbid_r < cur_l_low or forbid_l > cur_l_high:
                    continue
                # 左边有可用区间，直接返回合法
                if forbid_l > cur_l_low:
                    return True
                # 缩紧左边界
                if forbid_r < cur_l_high:
                    cur_l_low = forbid_r + 1
                # 整个left区间被禁止，当前t不合法
                else:
                    cur_l_low = cur_l_high + 1
                    break
            if cur_l_low <= cur_l_high:
                return True
        return False

    while low <= high:
        mid = (low + high) // 2
        if is_valid(mid):
            ans = mid
            low = mid + 1
        else:
            high = mid - 1
    return ans

复杂度说明 #

• 基础版本（无索引）：时间复杂度为O(logn * |L|)，实现简单，适配绝大多数常规场景。
• 空间索引优化版本：提前对障碍物坐标排序后做范围过滤，每次校验仅检查s范围内的障碍物，平均时间复杂度可降到O(|L|log|L| + logn)，可适配n为1e9、|L|为1e6级别的超大规模场景。

内容的提问来源于stack exchange，提问作者volcanrb