组合公式
从m 个箱子中选出 n 个箱子
公式：\(C_{m}^{n}=\frac{m!}{n!(m-n)!)}\)
每种方式两两相邻球之间都有一个磁力，假设：
- 放置方式1的两两相邻球之间的磁力的最小值为a
- 放置方式2的两两相邻球之间的磁力的最小值为b
... - 放置方式X的两两相邻球之间的磁力的最小值为x
那么本题的题解就是 max(a, b, ..., x)。即求最大的最小磁力。
由于题目已经给了 n 个篮子的位置 position，我们先将 position 升序，则可得出： - 两球之间的磁力最大值 = position[n-1] - postion[0]
- 由于数组每个值都不同，所以磁力最小值 = 1
接下来就可以用二分策略，求得一个中间值mid = (min + max) / 2，然后将mid值作为两球之间的最小间距dis，如果有放置策略可以满足所有两两相邻球之间的距离都大于等于dis，则dis就是本题的一个可能解。
public boolean isValid(int[] position, int len, int m){
int count = 1;
int pre = position[0];
for (int i = 1; i < position.length; i++) {
if (position[i] - pre >= len){
count++;
pre = position[i];
}
}
return count >= m;
}
整体代码：
class Solution {
// 所有 position 中的整数 互不相同
public int maxDistance(int[] position, int m) { // m 个球
Arrays.sort(position);
int max = position[position.length - 1] - position[0];
int min = 1;
int res= 1;
while (min <= max){
int mid = min + (max - min) / 2;
if (isValid(position, mid, m)){ // 尽量大一些
res = Math.max(res, mid);
min = mid + 1;
}else {
max = mid - 1;
}
}
return res;
}
public boolean isValid(int[] position, int len, int m){
int count = 1;
int pre = position[0];
for (int i = 1; i < position.length; i++) {
if (position[i] - pre >= len){
count++;
pre = position[i];
}
}
return count >= m;
}
}