Medium

题目描述

在宇宙 Earth C-137 中，Rick 发现了一种特殊的磁力形式，当两个球被放在他新发明的篮子里时会产生磁力。Rick 有 n 个空篮子，第 i 个篮子在位置 position[i]。Morty 有 m 个球，需要将球分配到篮子中，使得任意两个球之间的最小磁力最大。

Rick 指出，位置 x 和 y 处两个不同球之间的磁力是 |x - y|。

给定整数数组 position 和整数 m，返回所需的磁力。

示例 1：

输入：position = [1,2,3,4,7], m = 3
输出：3
解释：将 3 个球分别放在位置 1、4 和 7 的篮子中，球对之间的磁力为 [3, 3, 6]。最小磁力为 3。我们无法达到比 3 更大的最小磁力。

示例 2：

输入：position = [5,4,3,2,1,1000000000], m = 2
输出：999999999
解释：我们可以使用位置 1 和 1000000000 的篮子。

约束条件：

  • n == position.length
  • 2 <= n <= 10^5
  • 1 <= position[i] <= 10^9
  • position 中的所有整数都是不同的
  • 2 <= m <= position.length

解题思路

这是一个经典的二分搜索 + 贪心验证的问题。

核心思路：

  1. 问题转化：我们需要找到最大的最小距离。如果能以距离 x 放置 m 个球，那么也能以更小的距离放置；反之，如果不能以距离 x 放置，那么更大的距离也不行。这说明答案具有单调性，可以用二分搜索。

  2. 二分搜索范围：

    • 最小可能距离：1（相邻两个位置的最小差值）
    • 最大可能距离：(max_pos - min_pos)（最远两个位置的距离）

  3. 贪心验证策略：给定一个距离 mid，判断是否能放置 m 个球：

    • 将数组排序
    • 贪心地放置球：第一个球放在最左边，之后每个球都放在距离上一个球至少 mid 距离的最左位置
    • 如果能放下 m 个球，说明距离 mid 可行

  4. 算法流程：

    • 对位置数组排序
    • 二分搜索最大的可行距离
    • 对每个候选距离，用贪心算法验证是否可行

时间复杂度主要来自排序 O(n log n) 和二分搜索中的验证 O(n log(max_distance))。

代码实现

class Solution {
public:
    int maxDistance(vector<int>& position, int m) {
        sort(position.begin(), position.end());
        
        int left = 1, right = position.back() - position[0];
        int result = 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canPlace(position, m, mid)) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
    
private:
    bool canPlace(vector<int>& position, int m, int minDist) {
        int count = 1;
        int lastPos = position[0];
        
        for (int i = 1; i < position.size(); i++) {
            if (position[i] - lastPos >= minDist) {
                count++;
                lastPos = position[i];
                if (count >= m) return true;
            }
        }
        
        return false;
    }
};

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        
        def can_place(min_dist):
            count = 1
            last_pos = position[0]
            
            for i in range(1, len(position)):
                if position[i] - last_pos >= min_dist:
                    count += 1
                    last_pos = position[i]
                    if count >= m:
                        return True
            return False
        
        left, right = 1, position[-1] - position[0]
        result = 1
        
        while left <= right:
            mid = (left + right) // 2
            if can_place(mid):
                result = mid
                left = mid + 1
            else:
                right = mid - 1
        
        return result

public class Solution {
    public int MaxDistance(int[] position, int m) {
        Array.Sort(position);
        
        int left = 1, right = position[position.Length - 1] - position[0];
        int result = 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (CanPlace(position, m, mid)) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
    
    private bool CanPlace(int[] position, int m, int minDist) {
        int count = 1;
        int lastPos = position[0];
        
        for (int i = 1; i < position.Length; i++) {
            if (position[i] - lastPos >= minDist) {
                count++;
                lastPos = position[i];
                if (count >= m) return true;
            }
        }
        
        return false;
    }
}

var maxDistance = function(position, m) {
    position.sort((a, b) => a - b);
    
    const canPlace = (minDist) => {
        let count = 1;
        let lastPos = position[0];
        
        for (let i = 1; i < position.length; i++) {
            if (position[i] - lastPos >= minDist) {
                count++;
                lastPos = position[i];
                if (count >= m) return true;
            }
        }
        return false;
    };
    
    let left = 1, right = position[position.length - 1] - position[0];
    let result = 1;
    
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (canPlace(mid)) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型时间复杂度空间复杂度
时间复杂度O(n log n + n log(max_distance))O(1)
空间复杂度O(1)O(1)

说明：

  • 时间复杂度：排序需要 O(n log n)，二分搜索需要 O(log(max_distance)) 次，每次验证需要 O(n)
  • 空间复杂度：只使用了常数额外空间（不考虑排序的空间开销）

相关题目