Kimi LeetCode 3464. 正方形上的点之间的最大距离 Python3实现

LeetCode 3464. 正方形上的点之间的最大距离 — Python3 实现题目概述给定正方形边长 side以及位于正方形边界上的若干点。需要从中选出 k 个点使得任意两点之间的最小曼哈顿距离最大化。- 曼哈顿距离|x1 - x2| |y1 - y2|- 关键约束k 25points.length 15000核心思路这是一个经典的 最大化最小值 问题标准解法是二分答案 可行性检验。关键观察1. 答案上界为 side因为 k 4至少有两个点在同一条边上或相邻边上而同一/相邻边上的点距离最大为 side当 k4 时选四个角最小距离恰好为 side。2. 展开为正方形周长将正方形边界展开为一维环形数组周长 4 * side按顺时针顺序排列所有点。这样相邻点之间的距离可以用曼哈顿距离表示。展开映射规则- 左边 x0d y- 上边 ysided side x- 右边 xsided 3 * side - y- 下边 y0d 4 * side - x3. 可行性检验对于候选距离 limit检查是否能选出 k 个点使得相邻点包括首尾环绕的曼哈顿距离都 limit。由于 k 25可以枚举每个点作为起点贪心选择下一个满足距离要求的点。Python3 实现pythonimport bisectfrom typing import Listclass 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 yelif y side:# 上边从 (0, side) 向右到 (side, side)d side xelif x side:# 右边从 (side, side) 向下到 (side, 0)d 3 * side - yelse:# 下边从 (side, 0) 向左到 (0, 0)d 4 * side - xpositions.append(d)positions.sort()perimeter 4 * sidedef can_pick(limit: int) - bool:检查是否能选出 k 个点相邻点距离 limit包括首尾环绕# 枚举每个点作为起点for start_idx in range(n):start positions[start_idx]# 最后一个点不能超过 start perimeter - limit保证首尾环绕距离 limitlast_allowed start perimeter - limitcurrent startpicked 1for _ 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:breakcurrent positions[next_idx]picked 1else:# 成功选了 k 个点return Truereturn False# 二分搜索答案 [1, side]left, right 1, sideans 0while left right:mid (left right) // 2if can_pick(mid):ans midleft mid 1else:right mid - 1return 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)示例验证输入 输出 说明side2, points[[0,2],[2,0],[2,2],[0,0]], k4 2 四个角最小距离为 2side2, points[[0,0],[1,2],[2,0],[2,2],[2,1]], k4 1 选 (0,0), (2,0), (2,2), (2,1)side2, points[[0,0],[0,1],[0,2],[1,2],[2,0],[2,2],[2,1]], k5 1 选 (0,0), (0,1), (0,2), (1,2), (2,2)注意事项上述实现基于 展开贪心 的经典方法。但需要注意在展开为一维坐标后相邻边的点之间的曼哈顿距离与一维距离的关系需要仔细处理。对于 limit side 的情况展开方法能正确工作因为- 同一边上的点一维距离 曼哈顿距离- 相邻边上的点一维距离 曼哈顿距离- 对边上的点曼哈顿距离 side limit不会成为瓶颈如果追求更严谨的实现可以参考使用 双端队列 DP 的方法如搜索结果中的 Sequence 类实现它直接在二维坐标上用滑动窗口维护最长合法子序列。