(0,

如果一个点位于正方形的边上或者在边以内则认为该点位于正方形内。

正方形的边长可以为零。

输入points

[[2,2],[-1,-2],[-4,4],[-3,1],[3,-3]],

abdca

已知题目要求我们找到一个合法的正方形中心在0,0边平行于坐标轴并且正方形内不能有两个点的标签相同。

我么需要返回这样一个合法正方形内可以包含的最多点。

示例分析

示例1在标签a和b的最小距离都小于所有标签的次小距离的情况下可以容纳最多的点数是2。

示例2因为只有标签a的最小距离小于次小距离所以结果是1.示例3所有点都无法单独构成合法的正方形所以结果是0。

解题思路

正方形的中心为0,0。

正方形的边长可以从0开始逐渐增加。

在正方形的边界或内部不能有两个标签相同的点。

2.距离计算

maxabsxabsy。

这样边长为2*d的正方形可以刚好覆盖这个点。

选择最大的绝对值是因为正方形的边需要平行于坐标轴确保正方形能够完全包含点xy。

3.最小距离更新

min1数组用于记录每个标签对应的最小距离。

min1[j]表示标签为j的点中到原点的最小距离。

这个最小距离表示对于每个标签j能使其位于正方形内的最小正方形边长。

min2变量用于记录所有标签中的次小最小距离。

这意味着所有标签的最小距离中第二小的值。

这个值的意义在于如果某个标签的最小距离小于min2我们就能够确保在正方形中只包含这一标签而不包含其他可能导致标签冲突的点。

换句话说标签j的最小距离min1[j]小于min2以为着子在该标签的正方形内部不会有其他标签的点也即不会有标签重复的情况。

4.判断合法性

如果一个标签的最小距离min1[j]小于min2则可以认为这个标签可以包含在合法正方形中。

这是因为min2是次小的最小距离任何小于min2的标签距离都不会导致重复的标签出现。

5.最大化点数

计算并返回所有满足条件的标签的数量这个数量即是哈法正方形内可以包含的最多点数。

代码示例

{//如果标签的最小距离小于次小距离则认为其可以包含在合法正方形中res;//增加合法点数计数}}return

res;//返回合法点数