调试中...
困难
相关标签
相关企业
提示
给你一个整数 side，表示一个正方形的边长，正方形的四个角分别位于笛卡尔平面的 (0, 0) ，(0, side) ，(side, 0) 和 (side, side) 处。
同时给你一个 正整数 k 和一个二维整数数组 points，其中 points[i] = [xi, yi] 表示一个点在正方形边界上的坐标。
你需要从 points 中选择 k 个元素，使得任意两个点之间的 最小 曼哈顿距离 最大化 。
返回选定的 k 个点之间的 最小 曼哈顿距离的 最大 可能值。
两个点 (xi, yi) 和 (xj, yj) 之间的曼哈顿距离为 |xi - xj| + |yi - yj|。
示例 1：
输入： 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)。
示例 3：
输入： 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)。
提示：
1 <= side <= 1094 <= points.length <= min(4 * side, 15 * 103)points[i] == [xi, yi]- 输入产生方式如下：
points[i]位于正方形的边界上。- 所有
points[i]都 互不相同 。
4 <= k <= min(25, points.length)
通过次数
991
提交次数
2.5K
通过率
39.0%
相关企业
提示 1
Can we use binary search for this problem?
提示 2
Think of the coordinates on a straight line in clockwise order.
提示 3
Binary search on the minimum Manhattan distance
x.提示 4
During the binary search, for each coordinate, find the immediate next coordinate with distance >=
x.提示 5
Greedily select up to
k coordinates.相似题目
评论 (0)
贡献者
© 2025 领扣网络（上海）有限公司
0 人在线