Hard

题目描述

给你一个整数 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 <= 10^9
  • 4 <= points.length <= min(4 * side, 15 * 10^3)
  • points[i] == [xi, yi]
  • 输入保证：
    • points[i] 位于正方形的边界上
    • 所有 points[i] 都是唯一的
  • 4 <= k <= min(25, points.length)

解题思路

这道题的核心思路是使用二分搜索配合贪心算法。

首先，我们需要将正方形边界上的点按顺时针顺序排列。将正方形的四条边分别处理：

  • 下边：(x, 0) 其中 0 ≤ x ≤ side
  • 右边：(side, y) 其中 0 < y ≤ side
  • 上边：(x, side) 其中 0 ≤ x < side，按 x 降序
  • 左边：(0, y) 其中 0 < y < side，按 y 降序

为了计算边界上任意两点的曼哈顿距离，我们需要将二维问题转换为一维。通过给每个点分配一个"边界位置"，使得相邻两点在边界上的距离对应其曼哈顿距离。

接下来使用二分搜索答案：

  • 左边界：0（最小可能距离）
  • 右边界：正方形周长的一半（最大可能距离）
  • 对于每个候选距离 mid，使用贪心策略验证是否能选出 k 个点，使得任意两点距离都 ≥ mid

贪心策略：从第一个点开始，每次选择距离当前选中点至少为 mid 的下一个点。如果能选出 k 个点，说明答案至少为 mid。

时间复杂度优化：由于正方形周长较大但点数有限，我们将所有可能的距离值预先计算并排序，这样二分搜索的范围大大缩小。

代码实现

class Solution {
public:
    int maxDistance(int side, vector<vector<int>>& points, int k) {
        // 将点按顺时针顺序排列在边界上
        vector<pair<long long, int>> boundary;
        
        for (int i = 0; i < points.size(); i++) {
            int x = points[i][0], y = points[i][1];
            long long pos;
            
            if (y == 0) { // 下边
                pos = x;
            } else if (x == side) { // 右边
                pos = (long long)side + y;
            } else if (y == side) { // 上边
                pos = (long long)2 * side + (side - x);
            } else { // 左边 (x == 0)
                pos = (long long)3 * side + (side - y);
            }
            boundary.push_back({pos, i});
        }
        
        sort(boundary.begin(), boundary.end());
        
        // 计算所有可能的距离值
        set<int> distSet;
        long long perimeter = 4LL * side;
        
        for (int i = 0; i < boundary.size(); i++) {
            for (int j = i + 1; j < boundary.size(); j++) {
                long long diff = boundary[j].first - boundary[i].first;
                int dist = (int)min(diff, perimeter - diff);
                distSet.insert(dist);
            }
        }
        
        vector<int> distances(distSet.begin(), distSet.end());
        sort(distances.begin(), distances.end());
        
        // 二分搜索
        int left = 0, right = distances.size() - 1, answer = 0;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            int target = distances[mid];
            
            if (canSelect(boundary, k, target, perimeter)) {
                answer = target;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return answer;
    }
    
private:
    bool canSelect(const vector<pair<long long, int>>& boundary, int k, int minDist, long long perimeter) {
        int selected = 1;
        long long lastPos = boundary[0].first;
        
        for (int i = 1; i < boundary.size() && selected < k; i++) {
            long long currentPos = boundary[i].first;
            long long diff = currentPos - lastPos;
            int dist = (int)min(diff, perimeter - diff);
            
            if (dist >= minDist) {
                selected++;
                lastPos = currentPos;
            }
        }
        
        return selected >= k;
    }
};

class Solution:
    def maxDistance(self, side: int, points: List[List[int]], k: int) -> int:
        # 将点按顺时针顺序排列在边界上
        boundary = []
        
        for i, (x, y) in enumerate(points):
            if y == 0:  # 下边
                pos = x
            elif x == side:  # 右边
                pos = side + y
            elif y == side:  # 上边
                pos = 2 * side + (side - x)
            else:  # 左边 (x == 0)
                pos = 3 * side + (side - y)
            boundary.append((pos, i))
        
        boundary.sort()
        
        # 计算所有可能的距离值
        dist_set = set()
        perimeter = 4 * side
        
        for i in range(len(boundary)):
            for j in range(i + 1, len(boundary)):
                diff = boundary[j][0] - boundary[i][0]
                dist = min(diff, perimeter - diff)
                dist_set.add(dist)
        
        distances = sorted(list(dist_set))
        
        # 二分搜索
        left, right, answer = 0, len(distances) - 1, 0
        
        while left <= right:
            mid = (left + right) // 2
            target = distances[mid]
            
            if self.can_select(boundary, k, target, perimeter):
                answer = target
                left = mid + 1
            else:
                right = mid - 1
        
        return answer
    
    def can_select(self, boundary, k, min_dist, perimeter):
        selected = 1
        last_pos = boundary[0][0]
        
        for i in range(1, len(boundary)):
            if selected >= k:
                break
            current_pos = boundary[i][0]
            diff = current_pos - last_pos
            dist = min(diff, perimeter - diff)
            
            if dist >= min_dist:
                selected += 1
                last_pos = current_pos
        
        return selected >= k

public class Solution {
    public int MaxDistance(int side, int[][] points, int k) {
        // 将点按顺时针顺序排列在边界上
        List<(long pos, int index)> boundary = new List<(long, int)>();
        
        for (int i = 0; i < points.Length; i++) {
            int x = points[i][0], y = points[i][1];
            long pos;
            
            if (y == 0) { // 下边
                pos = x;
            } else if (x == side) { // 右边
                pos = (long)side + y;
            } else if (y == side) { // 上边
                pos = (long)2 * side + (side - x);
            } else { // 左边 (x == 0)
                pos = (long)3 * side + (side - y);
            }
            boundary.Add((pos, i));
        }
        
        boundary.Sort();
        
        // 计算所有可能的距离值
        HashSet<int> distSet = new HashSet<int>();
        long perimeter = 4L * side;
        
        for (int i = 0; i < boundary.Count; i++) {
            for (int j = i + 1; j < boundary.Count; j++) {
                long diff = boundary[j].pos - boundary[i].pos;
                int dist = (int)Math.Min(diff, perimeter - diff);
                distSet.Add(dist);
            }
        }
        
        List<int> distances = new List<int>(distSet);
        distances.Sort();
        
        // 二分搜索
        int left = 0, right = distances.Count - 1, answer = 0;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            int target = distances[mid];
            
            if (CanSelect(boundary, k, target, perimeter)) {
                answer = target;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return answer;
    }
    
    private bool CanSelect(List<(long pos, int index)> boundary, int k, int minDist, long perimeter) {
        int selected = 1;
        long lastPos = boundary[0].pos;
        
        for (int i = 1; i < boundary.Count && selected < k; i++) {
            long currentPos = boundary[i].pos;
            long diff = currentPos - lastPos;
            int dist = (int)Math.Min(diff, perimeter - diff);
            
            if (dist >= minDist) {
                selected++;
                lastPos = currentPos;
            }
        }
        
        return selected >= k;
    }
}

var maxDistance = function(side, points, k) {
    function manhattanDist(p1, p2) {
        return Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);
    }
    
    function canSelect(minDist) {
        const n = points.length;
        const dp = new Array(1 << n).fill(0);
        
        for (let mask = 0; mask < (1 << n); mask++) {
            const count = __builtin_popcount(mask);
            if (count <= 1) {
                dp[mask] = count;
                continue;
            }
            
            for (let i = 0; i < n; i++) {
                if ((mask & (1 << i)) === 0) continue;
                
                const prevMask = mask ^ (1 << i);
                let valid = true;
                
                for (let j = 0; j < n; j++) {
                    if (j === i || (prevMask & (1 << j)) === 0) continue;
                    if (manhattanDist(points[i], points[j]) < minDist) {
                        valid = false;
                        break;
                    }
                }
                
                if (valid) {
                    dp[mask] = Math.max(dp[mask], dp[prevMask] + 1);
                }
            }
        }
        
        return Math.max(...dp) >= k;
    }
    
    function __builtin_popcount(n) {
        let count = 0;
        while (n) {
            count++;
            n &= n - 1;
        }
        return count;
    }
    
    let left = 0, right = 4 * side;
    let result = 0;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (canSelect(mid)) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度值
时间复杂度O(n² log n)
空间复杂度O(n²)

其中 n 是点的数量。时间复杂度主要来自于计算所有可能距离值的 O(n²) 和对距离排序的 O(n² log n)，以及二分搜索中每次验证的 O(n) 操作。空间复杂度主要用于存储所有可能的距离值。

相关题目