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 addK
more gas stations so that D, the maximum distance between adjacent gas stations, is minimized.
Return the smallest possible value of D.
Example:
Input: stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], K = 9
Output: 0.500000
Note:
stations.length
will be an integer in range[10, 2000]
.stations[i]
will be an integer in range[0, 10^8]
.K
will be an integer in range[1, 10^6]
.Answers within
10^-6
of 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。
class Solution {
public double minmaxGasDist(int[] stations, int K) {
double end = Integer.MIN_VALUE;
for (int i = 1; i < stations.length; i++) {
end = Math.max(end, stations[i] - stations[i - 1]);
}
double start = 0, mid = 0;
while (end - start > 1e-6) {
mid = start + (end - start) / 2;
if (isValid(stations, K, mid)) {
end = mid;
}
else {
start = mid;
}
}
return start;
}
public boolean isValid(int[] stations, int K, double target) {
int count = 0;
for (int i = 1; i < stations.length; i++) {
count += (stations[i] - stations[i - 1]) / target;
}
return count <= K;
}
}
3. Time & Space Complexity
Binary Search: 时间复杂度O(nlogm), n为stations的个数,M是原来stations之间的距离和。 空间复杂度O(1)
Last updated
Was this helpful?