LeetCode 3464. 正方形上的点之间的最大距离——二分答案 环上贪心超详细图解 完整代码一、题目概述1.1 题目描述给定一个边长为side的正方形正方形四个顶点坐标固定为\(0, 0\)、\(side, 0\)、\(side, side\)、\(0, side\)。所有给定的点均落在正方形的四条边界上且所有点坐标互不重复。现在需要从所有边界点中挑选出k个点满足核心条件最大化所选点集中两两之间的最小曼哈顿距离。最终返回这个最大的最小曼哈顿距离。两点曼哈顿距离公式d∣x1−x2∣∣y1−y2∣d |x_1 - x_2| |y_1 - y_2|d∣x1​−x2​∣∣y1​−y2​∣1.2 题目重难点分析题型归类最大化最小值经典问题算法模板优先考虑二分答案核心难点点分布在正方形环形边界上常规二维距离计算复杂无法直接贪心关键限制k ≤ 25数值极小n ≤ 15000可支持线性小常数复杂度算法数据范围side ≤ 10^9无法遍历模拟必须用二分降维1.3 示例解读示例1side2,points[[0,2],[2,0],[2,2],[0,0]],k4输出2选取全部4个顶点四个点均匀分布在正方形边界两两最小曼哈顿距离为2为最优解。示例2side2,points[[0,0],[1,2],[2,0],[2,2],[2,1]],k4输出1最优选点\(0, 0\)、\(2, 0\)、\(2, 2\)、\(2, 1\)点集中最小曼哈顿距离为1无法找到更大的合法距离。二、核心解题思路问题转化2.1 关键数学结论解题核心对于正方形边界上的任意两点其曼哈顿距离 两点沿正方形边界的最短弧长。基于该结论我们可以将二维平面点问题完全转化为一维环形区间选点问题极大降低解题难度。2.2 二维坐标转一维环坐标我们规定从起点\(0,0\)出发顺时针沿正方形边界遍历将边界上的每个点映射为一维坐标t环形总周长L 4 \* side所有t的取值范围为\[0, L\)。四条边的映射规则底边y0从左到右t x右边xside从下到上t side \ y顶边yside从右到左t 3 \* side \- x左边x0从上到下t 4 \* side \- y坐标映射工具函数内嵌主代码# 二维边界坐标转一维环坐标t[]forx,yinpoints:ify0:# 底边t.append(x)elifxside:# 右边t.append(sidey)elifyside:# 顶边t.append(3*side-x)else:# 左边 x 0t.append(4*side-y)2.3 问题最终转化原问题等价于在长度为L4\*side的圆环上有n个定点选取k个点使得所有点两两之间的最短环距的最小值最大。标准的二分答案 贪心校验模板题。三、完整算法设计3.1 二分答案框架二分范围确定最小可能距离1最大可能距离2 \* side正方形对角点最大曼哈顿距离半环长二分逻辑枚举距离mid校验是否能选出k个点满足所有点间距 ≥mid。若可行尝试更大距离否则缩小距离。3.2 核心check(D) 可行性校验函数功能判断是否存在一种选点方案使得选出的k个点任意两点的环上最短距离 ≥D。步骤1破环为链环形问题最难处理首尾衔接问题通过数组加倍破环为链将所有一维坐标 周长L追加到原数组后得到长度为2n的扩展数组覆盖所有环形遍历场景。extt[xLforxint]步骤2双指针预处理下一可行点预处理next\_pos数组next\_pos\[i\]表示从ext\[i\]出发第一个距离 ≥D的点的下标。双指针单次遍历即可完成预处理时间复杂度O\(n\)。m2*n next_pos[m]*m j0foriinrange(m):ifji:ji# 找到第一个间距大于等于D的点whilejmandext[j]-ext[i]D:j1next_pos[i]j步骤3贪心选点校验枚举每一个原始点作为起点每次贪心选择最近的合法下一个点最优贪心策略预留最大空间给后续选点连续选取k\-1次。选完后额外校验首尾点环形间距是否合法。首尾校验条件ext\[cur\] \- ext\[i\] ≤ L \- D保证环上另一侧间距也 ≥ D。# 枚举所有原始起点foriinrange(n):curi# 贪心选取k-1个点for_inrange(k-1):curnext_pos[cur]ifcurin:# 超出一圈范围选点失败breakelse:# 首尾环形距离合法满足条件ifext[cur]-ext[i]L-D:returnTruereturnFalse四、完整可运行代码带详细注释fromtypingimportListclassSolution:defmaxDistance(self,side:int,points:List[List[int]],k:int)-int:# 1. 将正方形二维边界点映射为一维环形坐标t[]forx,yinpoints:ify0:# 底边(x,0)t.append(x)elifxside:# 右边(side,y)t.append(sidey)elifyside:# 顶边(x,side)t.append(3*side-x)else:# 左边(0,y)t.append(4*side-y)# 对一维坐标排序保证环形有序t.sort()nlen(t)L4*side# 正方形边界环形总周长# 2. 二分答案校验函数判断距离D是否可行defcheck(D:int)-bool:# 破环为链扩展数组处理环形首尾问题extt[xLforxint]m2*n next_pos[m]*m j0# 双指针预处理每个位置的下一个合法点foriinrange(m):ifji:jiwhilejmandext[j]-ext[i]D:j1next_pos[i]j# 枚举每一个原始点作为起点贪心选k个点forstartinrange(n):cur_idxstart# 贪心选择后续k-1个点for_inrange(k-1):cur_idxnext_pos[cur_idx]# 超出环形一圈范围选点失败ifcur_idxstartn:breakelse:# 成功选满k个点校验首尾环形距离ifext[cur_idx]-ext[start]L-D:returnTruereturnFalse# 3. 二分查找最大合法最小距离left,right1,2*side res0whileleftright:mid(leftright)//2ifcheck(mid):# 当前距离可行尝试更大距离resmid leftmid1else:# 当前距离不可行缩小范围rightmid-1returnres五、复杂度详细分析5.1 时间复杂度坐标映射排序O(nlog⁡n)O(n \log n)O(nlogn)n 为点的数量二分次数O(log⁡(side))O(\log(side))O(log(side))side 最大 1e9二分最多32次单次check复杂度双指针预处理O(n)O(n)O(n) 贪心枚举O(nk)O(nk)O(nk)总复杂度O(nlog⁡nnklog⁡(side))O(n \log n nk \log(side))O(nlognnklog(side))数据极限下n15000k25运算量仅千万级完全满足题目时间限制。5.2 空间复杂度O(n)O(n)O(n)主要消耗为扩展数组ext和预处理数组next\_pos。六、算法正确性证明6.1 贪心策略正确性在固定起点、固定最小间距D的前提下每次选择最近的合法下一个点是最优策略。原因尽早选点可以让后续剩余区间更长拥有更大的选点空间是区间选点问题的经典最优贪心策略不会出现漏解。6.2 环形校验正确性破环为链后通过ext\[cur\] \- ext\[start\] ≤ L \- D可以严格保证所选点集在环形上的首尾间距 ≥ D彻底解决环形首尾衔接问题。七、解题总结与模板提炼7.1 本题核心技巧维度降维正方形边界曼哈顿距离 → 一维环形弧长化繁为简破环为链数组加倍处理环形首尾特殊约束二分答案解决最大化最小值通用问题双指针贪心高效校验可行性适配题目数据范围7.2 通用模板最大化最小值环形选点适用于所有「环形选k个点最大化最小间距」类题目坐标归一化/映射为一维环形坐标二分枚举答案距离破环为链双指针预处理可行点枚举起点贪心选点校验合法性