当前位置：首页 > news >正文

LeetCode 3464. 正方形上的点之间的最大距离——二分答案 + 环上贪心（超详细图解 + 完整代码）

news 2026/4/26 0:36:06

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 示例解读

示例1

side=2,points=[[0,2],[2,0],[2,2],[0,0]],k=4输出：2

选取全部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\)，点集中最小曼哈顿距离为1，无法找到更大的合法距离。

二、核心解题思路：问题转化

2.1 关键数学结论（解题核心）

对于正方形边界上的任意两点，其曼哈顿距离 = 两点沿正方形边界的最短弧长。

基于该结论，我们可以将二维平面点问题，完全转化为一维环形区间选点问题，极大降低解题难度。

2.2 二维坐标转一维环坐标

我们规定：从起点\(0,0\)出发，顺时针沿正方形边界遍历，将边界上的每个点映射为一维坐标t，环形总周长L = 4 \* side，所有t的取值范围为\[0, L\)。

四条边的映射规则：

底边（y=0）：从左到右，t = x
右边（x=side）：从下到上，t = side \+ y
顶边（y=side）：从右到左，t = 3 \* side \- x
左边（x=0）：从上到下，t = 4 \* side \- y

坐标映射工具函数（内嵌主代码）：

# 二维边界坐标转一维环坐标t=[]forx,yinpoints:ify==0:# 底边t.append(x)elifx==side:# 右边t.append(side+y)elify==side:# 顶边t.append(3*side-x)else:# 左边 x == 0t.append(4*side-y)

2.3 问题最终转化

原问题等价于：在长度为L=4\*side的圆环上，有n个定点，选取k个点，使得所有点两两之间的最短环距的最小值最大。

标准的二分答案 + 贪心校验模板题。

三、完整算法设计

3.1 二分答案框架

二分范围确定

最小可能距离：1
最大可能距离：2 \* side（正方形对角点最大曼哈顿距离，半环长）

二分逻辑：枚举距离mid，校验是否能选出k个点满足所有点间距 ≥mid。若可行，尝试更大距离；否则缩小距离。

3.2 核心：check(D) 可行性校验函数

功能：判断是否存在一种选点方案，使得选出的k个点，任意两点的环上最短距离 ≥D。

步骤1：破环为链

环形问题最难处理首尾衔接问题，通过数组加倍破环为链：将所有一维坐标 + 周长L追加到原数组后，得到长度为2n的扩展数组，覆盖所有环形遍历场景。

ext=t+[x+Lforxint]

步骤2：双指针预处理下一可行点

预处理next\_pos数组，next\_pos\[i\]表示从ext\[i\]出发，第一个距离 ≥D的点的下标。双指针单次遍历即可完成预处理，时间复杂度O\(n\)。

m=2*n next_pos=[m]*m j=0foriinrange(m):ifj<i:j=i# 找到第一个间距大于等于D的点whilej<mandext[j]-ext[i]<D:j+=1next_pos[i]=j

步骤3：贪心选点校验

枚举每一个原始点作为起点，每次贪心选择最近的合法下一个点（最优贪心策略，预留最大空间给后续选点），连续选取k\-1次。选完后额外校验首尾点环形间距是否合法。

首尾校验条件：ext\[cur\] \- ext\[i\] ≤ L \- D，保证环上另一侧间距也 ≥ D。

# 枚举所有原始起点foriinrange(n):cur=i# 贪心选取k-1个点for_inrange(k-1):cur=next_pos[cur]ifcur>=i+n:# 超出一圈范围，选点失败breakelse:# 首尾环形距离合法，满足条件ifext[cur]-ext[i]<=L-D:returnTruereturnFalse

四、完整可运行代码（带详细注释）

fromtypingimportListclassSolution:defmaxDistance(self,side:int,points:List[List[int]],k:int)->int:# 1. 将正方形二维边界点映射为一维环形坐标t=[]forx,yinpoints:ify==0:# 底边：(x,0)t.append(x)elifx==side:# 右边：(side,y)t.append(side+y)elify==side:# 顶边：(x,side)t.append(3*side-x)else:# 左边：(0,y)t.append(4*side-y)# 对一维坐标排序，保证环形有序t.sort()n=len(t)L=4*side# 正方形边界环形总周长# 2. 二分答案校验函数：判断距离D是否可行defcheck(D:int)->bool:# 破环为链，扩展数组处理环形首尾问题ext=t+[x+Lforxint]m=2*n next_pos=[m]*m j=0# 双指针预处理每个位置的下一个合法点foriinrange(m):ifj<i:j=iwhilej<mandext[j]-ext[i]<D:j+=1next_pos[i]=j# 枚举每一个原始点作为起点，贪心选k个点forstartinrange(n):cur_idx=start# 贪心选择后续k-1个点for_inrange(k-1):cur_idx=next_pos[cur_idx]# 超出环形一圈范围，选点失败ifcur_idx>=start+n:breakelse:# 成功选满k个点，校验首尾环形距离ifext[cur_idx]-ext[start]<=L-D:returnTruereturnFalse# 3. 二分查找最大合法最小距离left,right=1,2*side res=0whileleft<=right:mid=(left+right)//2ifcheck(mid):# 当前距离可行，尝试更大距离res=mid left=mid+1else:# 当前距离不可行，缩小范围right=mid-1returnres