774 Minimize Max Distance to Gas Station

# 1. Question

On a horizontal number line, we have gas stations at positions`stations, stations, ..., stations[N-1]`, where`N = stations.length`.
Now, we add`K`more 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.length`will be an integer in range`[10, 2000]`.
2. 2.
`stations[i]`will be an integer in range`[0, 10^8]`.
3. 3.
`K`will be an integer in range`[1, 10^6]`.
4. 4.
Answers within`10^-6`of the true value will be accepted as correct.

# 2. Implementation

(1) Binary Search

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)