LeetCode Hard 笔记：从 O(N²) 到倍增优化，破解正方形选点难题
0. 前言
今天死磕了一道 LeetCode Hard 题（3464. 正方形上的点之间的最大距离）。这道题最折磨人的地方不在于逻辑难想，而在于从 “逻辑正确” 到 “不超时间限制 (TLE)” 之间的那道鸿沟。
这篇文章记录了我从暴力思想到 $O(N \log N)$ 优化的全过程，希望能给同样在刷题路上“撞墙”的同学一点启发。
1. 核心矛盾：最大化最小值
题目要求：选出 $k$ 个点，让任意两点间的距离的最小值尽可能大。
算法直觉： 只要看到“最大化最小值”， 90% 的概率是 二分答案 (Binary Search on Answer)。 我们不去直接求那个最优距离 $d$，而是去“猜”一个距离 $mid$，然后通过一个 check(mid) 函数验证：在这个间距下，能不能塞下 $k$ 个点。
2. 建模第一步：降维打击 (2D -> 1D)
正方形上的坐标 $(x, y)$ 处理起来很麻烦。但点只在边上，我们可以把正方形“剪开”拉直。
我们将正方形周长设为 $L = 4 \times side$，将所有点映射到 $[0, L)$ 的直线上：
- 下边 $(x, 0) \to x$
- 右边 $(side, y) \to side + y$
- 上边 $(x, side) \to 3 \times side - x$
- 左边 $(0, y) \to 4 \times side - y$
注意： 映射完成后一定要对数组进行排序，这是后续贪心策略的前提。
3. 贪心校验：给未来留出空间
在 check(d) 函数中，我们使用贪心算法： 从第一个点开始选，只要遇到下一个点距离当前点 $\ge d$，就立即选上。
为什么要“贪心”地选？ 因为你越早选下一个点，就给后面的人留下了越宽敞的空间。这是一种局部最优导致全局最优的典型场景。
4. 跌过的坑：曼哈顿距离 vs 周长距离
这是我最初卡在 609/619 个用例的原因。
- 周长距离：顺着边框走。
曼哈顿距离：$ x_1 - x_2 + y_1 - y_2 $（可以“穿过”正方形内部抄近道）。
在校验 check(d) 时，必须使用真实的曼哈顿距离。因为周长距离 $\ge$ 曼哈顿距离，如果只用坐标差计算，会高估两点间的距离，导致结果偏大。
5. 终极优化：倍增法 (Binary Lifting)
当 $N$ 达到 $10^5$ 时，$O(N^2)$ 的枚举起点会直接 TLE。我们需要用倍增法把跳跃过程从 $O(K)$ 降到 $O(\log K)$。
核心逻辑：
- 双指针预处理：算出每个点 $i$ 往后跳 1 步（满足距离 $\ge d$）会跳到哪个点，存入
jump[0][i]。 - 状态转移：
jump[p][i] = jump[p-1][jump[p-1][i]]。- 意思是：跳 $2^p$ 步，等于先跳 $2^{p-1}$ 步，再跳 $2^{p-1}$ 步。
- 二进制拆分：如果要跳 $k-1$ 步，通过二进制拆分（比如 $13 = 8 + 4 + 1$）在 $O(\log K)$ 时间内完成。
6. 完整代码 (Java)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 核心部分：倍增预处理与校验
private boolean check(Point[] pts, int k, int d, int[][] jump, int side) {
int n = pts.length;
// 1. 双指针找下一步
int r = 0;
for (int i = 0; i < n; i++) {
if (r <= i) r = i + 1;
while (r < i + n && getDist(pts[i], pts[r % n]) < d) r++;
jump[0][i] = r;
}
// 2. 倍增处理
for (int p = 1; p < jump.length; p++) {
for (int i = 0; i < n; i++) {
int mid = jump[p - 1][i];
if (mid >= i + n) jump[p][i] = mid;
else jump[p][i] = jump[p - 1][mid % n] + (mid / n) * n;
}
}
// 3. 验证起点
for (int i = 0; i < n; i++) {
int cur = i;
int steps = k - 1;
for (int p = 0; steps > 0; p++) {
if ((steps & 1) == 1) cur = jump[p][cur % n] + (cur / n) * n;
steps >>= 1;
}
if (cur < i + n && getDist(pts[i], pts[cur % n]) >= d) return true;
}
return false;
}