774 Minimize Max Distance to Gas Station

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:

Input: stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], K = 9

Output: 0.500000

Note:

1. stations.lengthwill be an integer in range[10, 2000].

2. stations[i]will be an integer in range[0, 10^8].

3. Kwill be an integer in range[1, 10^6].

4. Answers within10^-6of the true value will be accepted as correct.

2. Implementation

(1) Binary Search

思路: 题目要求要在stations数组中放入最多K个加油站，使stations之间的最大距离最小。这是一道根据函数判断二分方向的二分法题，这本质上是通过二分法找解的右边界， 我们要找到一个最小的distance，使得 K * distance >= 原来站之间的距离和。假设原来某两个加油站之间的距离是d，我们估算加了k个加油站的最大距离是m， 如果d/m >= 1，则加油站数量加一，通过叠加 d/m, 得到总共需要加的加油站数量，如果加油站数量小于等于k，则估算的距离m是一个有效解。

由于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)