LeetCode 3464. 正方形上的点之间的最大距离 — Python3 实现
题目概述
给定正方形边长 `side`，以及位于正方形边界上的若干点。需要从中选出 `k` 个点，使得任意两点之间的最小曼哈顿距离最大化。
- 曼哈顿距离：`|x1 - x2| + |y1 - y2|`
- 关键约束：`k <= 25`，`points.length <= 15000`
核心思路
这是一个经典的 "最大化最小值" 问题，标准解法是二分答案 + 可行性检验。
关键观察
1. 答案上界为 `side`：因为 `k >= 4`，至少有两个点在同一条边上或相邻边上，而同一/相邻边上的点距离最大为 `side`（当 `k=4` 时选四个角，最小距离恰好为 `side`）。
2. 展开为正方形周长：将正方形边界展开为一维环形数组（周长 `4 * side`），按顺时针顺序排列所有点。这样相邻点之间的距离可以用曼哈顿距离表示。
展开映射规则：
- 左边 `x=0`：`d = y`
- 上边 `y=side`：`d = side + x`
- 右边 `x=side`：`d = 3 * side - y`
- 下边 `y=0`：`d = 4 * side - x`
3. 可行性检验：对于候选距离 `limit`，检查是否能选出 `k` 个点，使得相邻点（包括首尾环绕）的曼哈顿距离都 `>= limit`。由于 `k <= 25`，可以枚举每个点作为起点，贪心选择下一个满足距离要求的点。
Python3 实现
```python
import bisect
from typing import List
class Solution:
def maxDistance(self, side: int, points: List[List[int]], k: int) -> int:
"""
二分答案 + 贪心可行性检验
将正方形边界展开为一维环形数组
"""
n = len(points)
positions = []
# 将边界点展开为一维坐标（顺时针方向）
for x, y in points:
if x == 0:
# 左边：从 (0,0) 向上到 (0, side)
d = y
elif y == side:
# 上边：从 (0, side) 向右到 (side, side)
d = side + x
elif x == side:
# 右边：从 (side, side) 向下到 (side, 0)
d = 3 * side - y
else:
# 下边：从 (side, 0) 向左到 (0, 0)
d = 4 * side - x
positions.append(d)
positions.sort()
perimeter = 4 * side
def can_pick(limit: int) -> bool:
"""
检查是否能选出 k 个点，相邻点距离 >= limit（包括首尾环绕）
"""
# 枚举每个点作为起点
for start_idx in range(n):
start = positions[start_idx]
# 最后一个点不能超过 start + perimeter - limit（保证首尾环绕距离 >= limit）
last_allowed = start + perimeter - limit
current = start
picked = 1
for _ in range(k - 1):
# 找下一个 >= current + limit 的点
next_idx = bisect.bisect_left(positions, current + limit)
# 如果超出数组范围，或者超出 last_allowed，则失败
if next_idx >= n or positions[next_idx] > last_allowed:
break
current = positions[next_idx]
picked += 1
else:
# 成功选了 k 个点
return True
return False
# 二分搜索答案 [1, side]
left, right = 1, side
ans = 0
while left <= right:
mid = (left + right) // 2
if can_pick(mid):
ans = mid
left = mid + 1
else:
right = mid - 1
return ans
```
复杂度分析
- 时间复杂度：`O(n log n + n * k * log n * log side)`
- 排序：`O(n log n)`
- 二分答案：`O(log side)` 次
- 每次检验：枚举 `n` 个起点，每个起点贪心选 `k` 个点，每次用二分查找 `O(log n)`
- 由于 `k <= 25`，实际运行很快
- 空间复杂度：`O(n)`
示例验证
输入 输出 说明
`side=2, points=[[0,2],[2,0],[2,2],[0,0]], k=4` `2` 四个角，最小距离为 2
`side=2, points=[[0,0],[1,2],[2,0],[2,2],[2,1]], k=4` `1` 选 (0,0), (2,0), (2,2), (2,1)
`side=2, points=[[0,0],[0,1],[0,2],[1,2],[2,0],[2,2],[2,1]], k=5` `1` 选 (0,0), (0,1), (0,2), (1,2), (2,2)
注意事项
上述实现基于 展开+贪心 的经典方法。但需要注意：在展开为一维坐标后，相邻边的点之间的曼哈顿距离与一维距离的关系需要仔细处理。对于 `limit <= side` 的情况，展开方法能正确工作，因为：
- 同一边上的点：一维距离 = 曼哈顿距离
- 相邻边上的点：一维距离 = 曼哈顿距离
- 对边上的点：曼哈顿距离 >= side >= limit，不会成为瓶颈
如果追求更严谨的实现，可以参考使用 双端队列 DP 的方法（如搜索结果中的 `Sequence` 类实现），它直接在二维坐标上用滑动窗口维护最长合法子序列。
