力扣3464. 正方形上的点之间的最大距离

题目

题目解析及思路

题目要求在points集合中找出k个点，k个点之间的最小的曼哈顿距离的最大值

最大最小值的题一般直接想到二分

将正方形往右展开成一条线，此时曼哈顿距离为两点直线距离**(仅起点右边的点)**

枚举起点二分答案，每次用二分找到>= st + mid的最近的点

代码

class Solution {
public:int maxDistance(int side, vector<vector<int>>& points, int k) {vector<long long> a;for(auto& p:points){int x = p[0],y = p[1];if (x == 0) {a.push_back(y);} else if (y == side) {a.push_back(side + x);} else if (x == side) {a.push_back(side * 3LL - y);} else {a.push_back(side * 4LL - x);}}ranges::sort(a);auto check = [&](int mid)->bool{//枚举起点for(long long st : a){//最右边的点的边界，当坐标超过边界时，该点与起点的距离已经<mid了，不满足条件long long end = side * 4LL + st - mid;long long cur = st;//找剩下k-1个点for(int i=0;i<k-1;i++){auto it = ranges::lower_bound(a,cur+mid);if(it == a.end() || *it > end){cur = -1;break;}cur = *it;}if(cur > 0){return true;}}return false;};int l = 1,r = side+1;while(l+1 < r){int mid = l + (r - l) / 2;if(check(mid)) l = mid;else r = mid;}return l;}
};