每日一题20250214-LC1552

题目信息

题目难度：Medium 掌握程度：🌟🌟🌟

在代号为 C-137 的地球上，Rick 发现如果他将两个球放在他新发明的篮子里，它们之间会形成特殊形式的磁力。Rick 有 n 个空的篮子，第 i 个篮子的位置在 position[i] ，Morty 想把 m 个球放到这些篮子里，使得任意两球间最小磁力最大。
已知两个球如果分别位于 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

解题思路

本题与 LC1760 类似，都是利用二分的思路来处理

具体思路如下：

我们可以「猜测」一个候选的最小距离 d ，然后验证是否存在一种放置方案，使得所有相邻球之间的距离均 ≥ d。
这个验证过程就是一个决策问题，其答案只有“可行”或“不行”。
然后我们对整个解空间进行二分，快速找到满足要求的 d 。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public int maxDistance(int[] position, int m) {
        Arrays.sort(position);
        int l = 1 ;
        int r = position[position.length-1] - position[0];
        int ans = -1;
        while(l <= r){
            int mid =  (l + r) / 2;
            if(check(mid,position,m)){
                ans = mid;
                l = mid + 1;
            }else{
                r = mid - 1;
            }

        }
        return ans;
    }

    private boolean check(int x , int[]position,int m){
        int cnt = 1;
        int pre = position[0];
        for(int i = 1 ; i < position.length; i++){
            if(position[i] - pre >= x ){
                pre = position[i];
                cnt++;
            }
        }
        return cnt >= m;
    }
}

扩展

对于 最大最小化问题 或者 最小最大化问题 ，我们都可以利用二分搜索来优化解题速度

这种问题都可以转化为 决策问题 ，我们可以「猜测」一个候选值，然后判断是否存在一个方案，使得所有条件都能满足这一要求。

对于我们猜测的候选值，他在解空间内是具有单调性的，比如对于候选值 X，如果“最小值至少为 X”这一条件可行，那么对于所有比 X 小的候选值通常也是可行的（或者在某些问题中恰好相反：如果 X 不可行，则所有比 X 大的候选值也不可行）。所以可以用 BinarySearch 而我们，二分搜索的收敛范围，是针对整个解空间的，而不是像普通的二分，是针对输入的数组

每日一题20250214-LC1552

题目信息

解题思路

扩展

相关文章：