以下是 LeetCode 3464 的 Java 实现，核心思路是二分答案 + 单调队列优化 DP。
解题思路
1. 二分答案：答案范围是 [0, \text{side}]，对最小曼哈顿距离进行二分搜索
2. 展开正方形：将正方形边界按顺时针展开为一维序列，按边分类排序
3. 可行性检验：对于候选距离 d，用单调队列优化的 DP 判断能否选出 k 个点，使得相邻点间曼哈顿距离 \ge d
完整代码
```java
import java.util.*;
class Solution {
public int maxDistance(int side, int[][] points, int k) {
List<int[]> ordered = getOrderedPoints(side, points);
int l = 0, r = side;
while (l < r) {
int m = (l + r + 1) / 2;
if (isValidDistance(ordered, k, m)) {
l = m;
} else {
r = m - 1;
}
}
return l;
}
// 判断能否选出 k 个点，使得相邻点间曼哈顿距离 >= d
private boolean isValidDistance(List<int[]> ordered, int k, int d) {
Deque<Sequence> dq = new ArrayDeque<>();
dq.add(new Sequence(ordered.get(0)[0], ordered.get(0)[1],
ordered.get(0)[0], ordered.get(0)[1], 1));
int maxLength = 1;
for (int i = 1; i < ordered.size(); i++) {
int x = ordered.get(i)[0];
int y = ordered.get(i)[1];
int startX = x, startY = y;
int length = 1;
// 维护单调队列：保留能作为起点的序列
while (!dq.isEmpty() && manhattan(x, y, dq.peekFirst().endX, dq.peekFirst().endY) >= d) {
Sequence first = dq.peekFirst();
if (manhattan(x, y, first.startX, first.startY) >= d
&& first.length + 1 >= length) {
startX = first.startX;
startY = first.startY;
length = first.length + 1;
maxLength = Math.max(maxLength, length);
}
dq.pollFirst();
}
dq.addLast(new Sequence(startX, startY, x, y, length));
}
return maxLength >= k;
}
// 曼哈顿距离
private int manhattan(int x1, int y1, int x2, int y2) {
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
}
// 将正方形边界上的点按顺时针顺序展开
private List<int[]> getOrderedPoints(int side, int[][] points) {
List<int[]> left = new ArrayList<>();
List<int[]> top = new ArrayList<>();
List<int[]> right = new ArrayList<>();
List<int[]> bottom = new ArrayList<>();
for (int[] point : points) {
int x = point[0], y = point[1];
if (x == 0 && y > 0) {
left.add(point);
} else if (x > 0 && y == side) {
top.add(point);
} else if (x == side && y < side) {
right.add(point);
} else {
bottom.add(point);
}
}
// 按顺时针方向排序各边上的点
left.sort(Comparator.comparingInt(p -> p[1])); // 左：y 从小到大
top.sort(Comparator.comparingInt(p -> p[0])); // 上：x 从小到大
right.sort((a, b) -> Integer.compare(b[1], a[1])); // 右：y 从大到小
bottom.sort((a, b) -> Integer.compare(b[0], a[0])); // 下：x 从大到小
List<int[]> ordered = new ArrayList<>();
ordered.addAll(left);
ordered.addAll(top);
ordered.addAll(right);
ordered.addAll(bottom);
return ordered;
}
// 记录序列信息
private static class Sequence {
int startX, startY; // 序列起点
int endX, endY; // 序列终点
int length; // 序列长度（包含的点数）
Sequence(int startX, int startY, int endX, int endY, int length) {
this.startX = startX;
this.startY = startY;
this.endX = endX;
this.endY = endY;
this.length = length;
}
}
}
```
关键点说明
要点 说明
二分答案 经典"最大化最小值"问题，答案范围 [0, \text{side}]，k \ge 4 时答案不超过 \text{side}
展开正方形 按顺时针将边界点排成一维序列：左(y↑)、上(x↑)、右(y↓)、下(x↓)
单调队列优化 DP 状态 `dp[i]` 表示以第 i 个点结尾的最长合法序列长度。利用单调性，队首维护最优起点
可行性检验 对于候选距离 d，检查是否存在长度 \ge k 的合法序列
复杂度分析
- 时间复杂度：O(n \log \text{side})，其中 n = \text{points.length}。二分搜索 O(\log \text{side})，每次检验 O(n)
- 空间复杂度：O(n)