774 Minimize Max Distance to Gas Station

1. Question

On a horizontal number line, we have gas stations at positionsstations[0], stations[1], ..., stations[N-1], whereN = stations.length.
Now, we addKmore gas stations so that D, the maximum distance between adjacent gas stations, is minimized.
Return the smallest possible value of D.
Example:
1
Input: stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], K = 9
2
3
Output: 0.500000
Copied!
Note:
  1. 1.
    stations.lengthwill be an integer in range[10, 2000].
  2. 2.
    stations[i]will be an integer in range[0, 10^8].
  3. 3.
    Kwill be an integer in range[1, 10^6].
  4. 4.
    Answers within10^-6of the true value will be accepted as correct.

2. Implementation

(1) Binary Search
思路: 题目要求要在stations数组中放入最多K个加油站,使stations之间的最大距离最小。这是一道根据函数判断二分方向的二分法题,这本质上是通过二分法找解的右边界, 我们要找到一个最小的distance,使得 K * distance >= 原来站之间的距离和。
由于stationss[i]的范围在0和10^8之间,那么将start初始为0, end初始为10^8,然后按照这个距离二分找出满足条件的距离。而isValid()就是判断二分方向的函数,其核心就是根据我们二分得到的candidate mid这个距离,我们计算stations之间按照这个距离评分的话我们需要多少个加油站,如果需要的加油站count > K,说明mid这个距离太小,所以start = mid, 如果count <= K,说明mid是个可能的解,将end = mid。
1
class Solution {
2
public double minmaxGasDist(int[] stations, int K) {
3
double end = Integer.MIN_VALUE;
4
5
for (int i = 1; i < stations.length; i++) {
6
end = Math.max(end, stations[i] - stations[i - 1]);
7
}
8
9
double start = 0, mid = 0;
10
11
while (end - start > 1e-6) {
12
mid = start + (end - start) / 2;
13
14
if (isValid(stations, K, mid)) {
15
end = mid;
16
}
17
else {
18
start = mid;
19
}
20
}
21
return start;
22
}
23
24
public boolean isValid(int[] stations, int K, double target) {
25
int count = 0;
26
for (int i = 1; i < stations.length; i++) {
27
count += (stations[i] - stations[i - 1]) / target;
28
}
29
return count <= K;
30
}
31
}
Copied!

3. Time & Space Complexity

Binary Search: 时间复杂度O(nlogm), n为stations的个数,M是原来stations之间的距离和。 空间复杂度O(1)