On a horizontal number line, we have gas stations at positions stations[0], stations[1], ..., 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:

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.

思路：首先如何使得每个station之间的最大距离最小，比如：两个station为[1, 9]，间隔为8。要插入一个station使得最大距离最小，插入后应该为[1, 5, 9]，最大间隔为4。如果插入后为[1, 6, 9], [1, 3, 9]，它们的最大间隔分别为5， 6，不是最小。可以看出，对于插入k个station使得最大间隔最小的唯一办法是均分。

一种贪心的做法是，找到最大的gap，插入1个station，依此类推，但很遗憾，这种贪心策略是错误的。问题的难点在于我们无法确定到底哪两个station之间需要插入station，插入几个station也无法得知。用DP会内存超标MLE，用堆会时间超标TLE。

换个思路，如果假设知道了答案会怎么样？因为知道了最大间隔，所以如果目前的两个station之间的gap没有符合最大间隔的约束，就必须添加新的station来让它们符合最大间隔的约束，这样对于每个gap能够求得需要添加station的个数。如果需求数<=K，说明还可以进一步减小最大间隔，直到需求数>K。

解法1: 优先队列，每次找出gap最大的一个区间，然后新加入一个station，直到所有的k个station都被加入，此时最大的gap即为所求。采用优先队列，使得每次最大的gap总是出现在队首。空间复杂度是O(n)，时间复杂度是O(klogn)，其中k是要加入的新station的个数，n是原有的station个数。这种方法应该没毛病，但是TLE

解法：二分法，判定条件不是简单的大小关系，而是根据子函数。minmaxGap的最小值left = 0，最大值right = stations[n - 1] - stations[0]。每次取mid为left和right的均值，然后计算如果mimaxGap为mid，那么最少需要添加多少个新的stations，记为count。如果count > K，说明均值mid选取的过小，必须新加更多的stations才能满足要求，更新left的值；否则说明均值mid选取的过大，使得需要小于K个新的stations就可以达到要求，寻找更小的mid，使得count增加到K。如果假设stations[N- 1] - stations[0] = m，空间复杂度是O(1)，时间复杂度是O(nlogm)，可以发现与k无关。

Java:

public double minmaxGasDist(int[] stations, int K) {

        int n = stations.length;

        double[] gap = new double[n - 1];

        for (int i = 0; i < n - 1; ++i) {

            gap[i] = stations[i + 1] - stations[i];

        }

        double lf = 0;

        double rt = Integer.MAX_VALUE;

        double eps = 1e-7;

        while (Math.abs(rt - lf) > eps) {

            double mid = (lf + rt) /2;

            if (check(gap, mid, K)) {

                rt = mid;

            }

            else {

                lf = mid;

            }

        }

        return lf;

    }

    boolean check(double[] gap, double mid, int K) {

        int count = 0;

        for (int i = 0; i < gap.length; ++i) {

            count += (int)(gap[i] / mid);

        }

        return count <= K;

    }

Python:

class Solution(object):

    def minmaxGasDist(self, stations, K):

        """

        :type stations: List[int]

        :type K: int

        :rtype: float

        """

        def possible(stations, K, guess):

            return sum(int((stations[i+1]-stations[i]) / guess)

                       for i in xrange(len(stations)-1)) <= K

        left, right = 0, 10**8

        while right-left > 1e-6:

            mid = left + (right-left)/2.0

            if possible(mid):

                right = mid

            else:

                left = mid

        return left

Python:

class Solution(object):

    def minmaxGasDist(self, st, K):

        """

        :type stations: List[int]

        :type K: int

        :rtype: float

        """

        lf = 1e-6

        rt = st[-1] - st[0]

        eps = 1e-7

        while rt - lf > eps:

            mid = (rt + lf) / 2

            cnt = 0

            for a, b in zip(st, st[1:]):

               cnt += (int)((b - a) / mid)

            if cnt <= K: rt = mid

            else: lf = mid

        return rt

Python:

class Solution(object):

    def minmaxGasDist(self, stations, K):

        """

        :type stations: List[int]

        :type K: int

        :rtype: float

        """

        stations.sort()

        step = 1e-9

        left, right = 0, 1e9

        while left <= right:

            mid = (left + right) / 2

            if self.isValid(mid, stations, K):

                right = mid - step

            else:

                left = mid + step

        return mid

    def isValid(self, gap, stations, K):

        for x in range(len(stations) - 1):

            dist = stations[x + 1] - stations[x]

            K -= int(math.ceil(dist / gap)) - 1

        return K >= 0

C++:

class Solution {

public:

    double minmaxGasDist(vector<int>& stations, int K) {

        double left = 0, right = 1e8;

        while (right - left > 1e-6) {

            double mid = left + (right - left) / 2;

            if (helper(stations, K, mid)) right = mid;

            else left = mid;

        }

        return left;

    }

    bool helper(vector<int>& stations, int K, double mid) {

        int cnt = 0, n = stations.size();

        for (int i = 0; i < n - 1; ++i) {

            cnt += (stations[i + 1] - stations[i]) / mid;

        }

        return cnt <= K;

    }

};

C++:

class Solution {

public:

    double minmaxGasDist(vector<int>& stations, int K) {

        double left = 0, right = 1e8;

        while (right - left > 1e-6) {

            double mid = left + (right - left) / 2;

            int cnt = 0, n = stations.size();

            for (int i = 0; i < n - 1; ++i) {

                cnt += (stations[i + 1] - stations[i]) / mid;

            }

            if (cnt <= K) right = mid;

            else left = mid;

        }

        return left;

    }

};

类似题目：

719. Find K-th Smallest Pair Distance

668. Kth Smallest Number in Multiplication Table

644. Maximum Average Subarray II

378. Kth Smallest Element in a Sorted Matrix

All LeetCode Questions List 题目汇总

巴特西

[LeetCode] 774. Minimize Max Distance to Gas Station 最小化加油站间的最大距离

All LeetCode Questions List 题目汇总

最新文章

热门文章