正方形内最大点数（LeetCode 3143）：二分答案与次小切比雪夫距离两种解法解析

导读

本文围绕 LeetCode 第 130 场双周赛 T2《Maximum Points Inside the Square》（正方形内最大点数，题目编号 3143）的官方题解展开，给出两种完整可落地的解法：二分边长（单调性二分）+ 位运算判重，以及 切比雪夫距离 + 维护次小值。读完本文，你既能掌握"二分答案"与"几何距离建模"这两类高频技巧在竞赛题中的组合用法，也能在该开源仓库中找到对应的 Go 实现与自动化测试用例，直接运行验证。

题目速览与仓库对应实现

原题要求：给定平面上若干点 points 与等长的标签字符串 s，求边平行于坐标轴、中心在原点的正方形内（含边界）能够容纳的、标签互不重复的最大点数。函数签名见官方题解：

maxPointsInsideSquare(points, s) -> int

在该仓库中，本题的完整配套位于 leetcode/biweekly/130/b/ 目录下：

文件	作用
README.md	官方题解全文（本文的骨架）
b.go	两种方法的 Go 实现
b.txt	3 组标准测试用例（输入 + 期望输出）
b_test.go	基于仓库测试工具的用例驱动测试

其中 b.go 实现了方法二（次小切比雪夫距离），b.go 中的 maxPointsInsideSquare2 实现了方法一（二分），两份实现与官方题解逐行对应，便于对照阅读。

方法一：二分边长（单调性二分 + 位运算判重）

单调性观察：边长越大越"不合法"

先刻画本题的核心单调性：正方形边长越大，可能覆盖的点越多，出现重复标签的概率越大，即"越不合法"。于是"是否存在某个边长使正方形内的标签全部互不重复"这个问题对边长而言具备二分的单调性，可以二分边长的一半 size（因为正方形中心在原点、边平行于坐标轴，点 (x, y) 在正方形内当且仅当 |x| <= size 且 |y| <= size）。

二分边界与"check 中更新答案"技巧

在二分过程中，check(size) 负责扫描所有点：统计落在正方形内的字符，若遇到重复字符则判定不合法；若全部不重复，则用本次遇到的字符个数更新答案最大值。

官方题解给出了一个关键 ⚠注意：虽然 check(0) 一定为 true（边长为 0 时正方形退化为原点，最多覆盖一个点，不会重复），但由于代码是在 check 内部更新答案的，为了保证边长为 0 时也能触发一次更新，二分范围必须包含 0（例如左边界从 -1 开始）。

答疑：为什么可以直接覆盖式更新 ans，不需要写 max？

问：为什么可以直接更新 ans，为什么不需要写 ans = max(ans, ...)？

答：更新 ans 时必然会伴随着二分区间左边界 left 的更新（即左边界被推进到一个更大的 size）。那么下一次更新 ans 时，正方形边长一定更长，覆盖的点数不会变少，因此新答案只增不减，可以直接覆盖赋值，无需写 max。这正是"二分答案配合状态内更新"的一个经典手法。

位运算技巧：用 int 充当集合

check 内部还使用了位运算代替哈希集合，原理可概括为三件套：

• vis >> c & 1 > 0：判断字符 c（c = s[i] - 'a'，取 0..25）是否已在集合中；
• vis |= 1 << c：把字符 c 加入集合；
• bits.OnesCount(vis) / Integer.bitCount(vis) / popcount(vis)：统计集合中的字符个数。

因为本题字符均为小写字母（|Σ| = 26），一个 32 位整数即可完整承载集合状态，判重与计数均为 O(1) 位运算。

四种语言实现

以下代码直接继承自官方题解，逻辑完全等价（Python 使用 bisect_left(..., key=check) 完成二分）：

class Solution:
    def maxPointsInsideSquare(self, points: List[List[int]], s: str) -> int:
        ans = 0
        def check(size: int) -> bool:
            vis = set()
            for (x, y), c in zip(points, s):
                if abs(x) <= size and abs(y) <= size:  # 点在正方形中
                    if c in vis:
                        return True
                    vis.add(c)
            nonlocal ans
            ans = len(vis)
            return False

        # 注意 range 并不会创建 list，它是 O(1) 的
        bisect_left(range(1_000_000_001), True, key=check)
        return ans

class Solution {
    private int ans;

    public int maxPointsInsideSquare(int[][] points, String S) {
        char[] s = S.toCharArray();
        int left = -1;
        int right = 1_000_000_001;
        while (left + 1 < right) {
            int mid = (left + right) >>> 1;
            if (check(mid, points, s)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return ans;
    }

    boolean check(int size, int[][] points, char[] s) {
        int vis = 0;
        for (int i = 0; i < points.length; i++) {
            // 判断点是否在正方形中
            if (Math.abs(points[i][0]) <= size && Math.abs(points[i][1]) <= size) {
                int c = s[i] - 'a';
                if ((vis >> c & 1) > 0) { // c 在集合中
                    return false;
                }
                vis |= 1 << c; // 把 c 加入集合
            }
        }
        ans = Integer.bitCount(vis);
        return true;
    }
}

class Solution {
public:
    int maxPointsInsideSquare(vector<vector<int>>& points, string s) {
        int ans = 0;

        auto check = & -> bool {
            int vis = 0;
            for (int i = 0; i < points.size(); i++) {
                // 判断点是否在正方形中
                if (abs(points[i][0]) <= size && abs(points[i][1]) <= size) {
                    char c = s[i] - 'a';
                    if (vis >> c & 1) { // c 在集合中
                        return false;
                    }
                    vis |= 1 << c; // 把 c 加入集合
                }
            }
            ans = popcount(1u * vis);
            return true;
        };

        int left = -1, right = 1'000'000'001;
        while (left + 1 < right) {
            int mid = (left + right) / 2;
            (check(mid) ? left : right) = mid;
        }
        return ans;
    }
};

func maxPointsInsideSquare(points [][]int, s string) (ans int) {
    sort.Search(1_000_000_001, func(size int) bool {
        vis := 0
        for i, p := range points {
            if abs(p[0]) <= size && abs(p[1]) <= size { // 点在正方形中
                c := s[i] - 'a'
                if vis>>c&1 > 0 { // c 在集合中
                    return true
                }
                vis |= 1 << c // 把 c 加入集合
            }
        }
        ans = bits.OnesCount(uint(vis))
        return false
    })
    return
}

func abs(x int) int { if x < 0 { return -x }; return x }

仓库中该方法的实际实现位于 b.go，与上方 Go 版逐行一致：使用 sort.Search(1e9+1, ...) 二分、vis>>c&1 判重、bits.OnesCount 计数，并复用了同一个 abs 辅助函数。

复杂度分析

• 时间复杂度：O(n log U)，其中 n 为 s 的长度，U = max(|x_i|, |y_i|)（本题坐标绝对值上限为 1e9，因此二分上界取 1e9+1，约 30 轮迭代）。
• 空间复杂度：O(|Σ|) 或 O(1)。其中 |Σ| 为字符集合的大小，本题字符均为小写字母，|Σ| = 26（Python 用 set 时为 O(|Σ|)，Java/C++/Go 用整数位集时为 O(1)）。

方法二：维护次小切比雪夫距离的最小值

核心建模：切比雪夫距离

定义点 (x, y) 到原点 (0, 0) 的切比雪夫距离为：

$$\max(|x|,|y|)$$

这与"点能否进入边长为 2*size 的中心原点正方形"判定完全一致：|x| <= size && |y| <= size 等价于该距离不超过 size。因此问题可转化为：随着正方形不断扩张，每个标签最早"可能发生冲突"的时刻，取决于该标签下所有点切比雪夫距离的分布。

关键定义与观察

定义 minD[c] 为标签 c 的所有点到原点的最小切比雪夫距离；minD2[c] 为标签 c 的所有点到原点的次小切比雪夫距离。

核心观察：一个标签若有两个点能同时进入正方形，那么冲突会在边长扩大到 minD2[c] 那一刻必然发生。因此"正方形内标签不重复"的充分必要条件为：对每个标签 c，其最小的那个点必须满足

$$\textit{minD}[c] < \textit{min}_2$$

其中 min2 是所有标签的 minD2 中的最小值（即"第二小的切比雪夫距离的最小值"）。换言之，只要标签 c 离原点最近的点比全局第一次可能冲突的半径还近，它就可以被安全地计入答案。

巧妙的实现：不维护 minD2，只维护 min2

代码实现时无需维护 minD2[c] 数组，只需在单次遍历中同时维护 minD[c] 与全局 min2：

• 当新点距离 d 比 minD[c] 更小时：旧的最小值 minD[c] 自然"降级"为该标签的次小值，用 min2 = min(min2, minD[c]) 更新全局次小，再把 minD[c] 更新为 d；
• 否则：d 可能就是该标签的次小值，直接 min2 = min(min2, d)。

最终答案 = 满足 minD[c] < min2 的标签个数。这一"降级更新"手法避免了为每个字符维护次小数组，把空间与代码量都压到了最低。

四种语言实现

class Solution:
    def maxPointsInsideSquare(self, points: List[List[int]], s: str) -> int:
        min_d = defaultdict(lambda: inf)
        min2 = inf
        for (x, y), c in zip(points, s):
            d = max(abs(x), abs(y))
            if d < min_d[c]:
                # d 是目前最小的，那么 min_d[c] 是次小的
                min2 = min(min2, min_d[c])
                min_d[c] = d
            else:
                # d 可能是次小的
                min2 = min(min2, d)
        return sum(d < min2 for d in min_d.values())

class Solution {
    public int maxPointsInsideSquare(int[][] points, String s) {
        int[] minD = new int[26];
        Arrays.fill(minD, Integer.MAX_VALUE);
        int min2 = Integer.MAX_VALUE;
        for (int i = 0; i < points.length; i++) {
            int d = Math.max(Math.abs(points[i][0]), Math.abs(points[i][1]));
            int c = s.charAt(i) - 'a';
            if (d < minD[c]) {
                // d 是目前最小的，那么 minD[c] 是次小的
                min2 = Math.min(min2, minD[c]);
                minD[c] = d;
            } else {
                // d 可能是次小的
                min2 = Math.min(min2, d);
            }
        }
        int ans = 0;
        for (int d : minD) {
            if (d < min2) {
                ans++;
            }
        }
        return ans;
    }
}

class Solution {
public:
    int maxPointsInsideSquare(vector<vector<int>>& points, string s) {
        int min_d[26], min2 = INT_MAX;
        ranges::fill(min_d, INT_MAX);
        for (int i = 0; i < points.size(); i++) {
            int d = max(abs(points[i][0]), abs(points[i][1]));
            char c = s[i] - 'a';
            if (d < min_d[c]) {
                // d 是目前最小的，那么 min_d[c] 是次小的
                min2 = min(min2, min_d[c]);
                min_d[c] = d;
            } else {
                // d 可能是次小的
                min2 = min(min2, d);
            }
        }
        int ans = 0;
        for (int d : min_d) {
            ans += d < min2;
        }
        return ans;
    }
};

func maxPointsInsideSquare(points [][]int, s string) (ans int) {
    minD := [26]int{}
    for i := range minD {
        minD[i] = math.MaxInt
    }
    min2 := math.MaxInt
    for i, p := range points {
        d := max(abs(p[0]), abs(p[1]))
        c := s[i] - 'a'
        if d < minD[c] {
            // d 是目前最小的，那么 minD[c] 是次小的
            min2 = min(min2, minD[c])
            minD[c] = d
        } else {
            // d 可能是次小的
            min2 = min(min2, d)
        }
    }
    for _, d := range minD {
        if d < min2 {
            ans++
        }
    }
    return
}

func abs(x int) int { if x < 0 { return -x }; return x }

仓库中的 b.go 即此实现：minD 用 [26]int 定长数组初始化 math.MaxInt，min2 同步维护，最后统计 d < min2 的标签个数。注意该版本直接用 max(abs(x), abs(y)) 计算切比雪夫距离，与判定式 |x|<=size && |y|<=size 严格等价。

复杂度分析

• 时间复杂度：O(n + |Σ|)，其中 n 为 s 的长度，|Σ| 为字符集合大小（本题 |Σ| = 26）。
• 空间复杂度：O(|Σ|)。

两种方法对比与选型

维度	方法一（二分边长）	方法二（次小切比雪夫距离）
核心思想	单调性二分 + 判定	距离建模 + 维护次小值
时间复杂度	O(n log U)	`O(n +
空间复杂度	`O(	Σ
代码技巧	二分边界含 0、check 内更新 ans	降级更新 min2，省去次小数组
适用特征	判定函数天然单调的"答案二分"题	需要把"冲突最早时刻"量化的几何/分组题

方法一把问题归约为"合法/非法的单调判定"，是二分答案题型的标准范式；方法二则直接从切比雪夫距离出发，把"每个标签最早冲突半径"提炼为全局次小值，一步到位，常数更小。两者互为印证：理解了方法二，再看方法一的 check 其实就是在二分那个"临界半径"。

仓库中的测试用例与验证

该题在仓库中配有可直接运行的自动化测试，测试数据保存在 b.txt，共 3 组（每组 3 行：points、s、期望输出）：

[[2,2],[-1,-2],[-4,4],[-3,1],[3,-3]]
"abdca"
2

[[1,1],[-2,-2],[-2,2]]
"abb"
1

[[1,1],[-1,-1],[2,-2]]
"ccd"
0

测试入口 b_test.go 通过仓库测试工具 leetcode/testutil/leetcode.go 的 RunLeetCodeFuncWithFile(t, maxPointsInsideSquare, "b.txt", 0) 完成用例驱动：该工具会按函数签名反射解析参数（fNumIn + fNumOut 行一组，此处为 2 入 1 出共 3 行一组），逐例调用并比对期望输出，逻辑见 RunLeetCodeFuncWithFile。在仓库根目录执行 go test ./leetcode/biweekly/130/b 即可复现验证方法二的实现。

从用例可直观验证算法正确性：第 1 组中标签 a、b、d、c、a 各一个点，a 的第二个点在 (-4,4) 距离更远，取最小距离集合时 a 只贡献最远能容纳的那个点，最终答案为 2；第 3 组中标签 c、c、d 在最小正方形内必然有一对 c 冲突，答案退化为 0——与"边界扩张到第一次冲突之前"的模型完全吻合。

延伸学习

• 二分查找红蓝染色法：方法一所用"二分答案 + 判定函数"的红蓝染色法基础原理，可参考《二分查找 红蓝染色法》基础算法精讲（B站"灵茶山艾府"系列）。
• 从集合论到位运算：方法一 vis >> c & 1、vis |= 1 << c 与 OnesCount 的组合，源自"用整数位表示集合"的常见位运算技巧总结（LeetCode 题解圈《从集合论到位运算，常见位运算技巧分类总结》）。
• 分类题单：作者在官方题解中给出的分类刷题清单，与本题直接相关的类别包括：二分算法（二分答案/最小化最大值/最大化最小值/第 K 小）、位运算（基础/性质/拆位/试填/恒等式/思维）、常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）等，可作为后续系统训练路线。
• 仓库配套：本题双周赛其余题目题解位于 leetcode/biweekly/130/，官方完整题解见 README.md；仓库的通用算法模板（二分、位运算、数据结构等）位于 copypasta/，可供实战复用。