3143 正方形中的最多点数

题目描述#

给定二维数组 points，其中 points[i] = [x_i, y_i] 表示第 i 个点的坐标；再给定字符串 s，s[i] 表示第 i 个点的标签。若一个以原点为中心、边与坐标轴平行的正方形内不存在标签相同的两点（边上视为在内），则称其为合法正方形。请返回合法正方形内最多可以容纳的点数。正方形的边长允许为 0。

思路#

这道题适合二分答案：我们二分正方形的半边长 mid，判断在这个范围内是否能保持标签唯一性。

二分区间#

半边长度可以从 0 开始，理论上上界可设置为一个明显的大值 1e9+1（大于题目坐标范围），保证搜索空间覆盖所有可能答案。
如果 mid 可行，说明还能继续扩张，于是左指针右移；反之缩小范围。

复杂度#

单次检查要遍历所有点，时间 O(n)。
二分次数约为 log(1e9)，整体复杂度 O(n log U)，其中 U 为半边长上界。
额外空间只用到了 26 长度的计数数组，为 O(1)。

代码#

class Solution {
    int ans = 0;

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

    public boolean check(int[][] points, int mid, char[] s) {
        int i = 0;
        int[] cnt = new int[26];
        int cur = 0;
        for (int[] p : points) {
            int x = p[0];
            int y = p[1];
            if (mid >= Math.abs(x) && mid >= Math.abs(y)) {
                cnt[s[i] - 'a']++;
                if (cnt[s[i] - 'a'] > 1) {
                    return false;
                }
                cur++;
            }
            i++;
        }
        ans = Math.max(ans, cur);
        return true;
    }
}

知识边界#

切比雪夫距离（Chebyshev Distance）：在网格上从 (x, y) 到 (0, 0) 的最少国王步数，公式为 max(|x|, |y|)。在本题中，它恰好对应轴对齐正方形的半边长。
如果正方形的中心或朝向发生变化，Chebyshev 距离不再直接适用，此时需要换用欧氏距离或旋转坐标系，同时重新设计二分的判定函数。

代码#

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;
    }
}

知识边界参考灵茶山艾府