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

2021年09月15日 阅读数:1
这篇文章主要向大家介绍[LeetCode] 774. Minimize Max Distance to Gas Station 最小化加油站间的最大距离,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

On a horizontal number line, we have gas stations at positions stations[0], stations[1], ..., stations[N-1], where N = stations.length.html

Now, we add K more gas stations so that D, the maximum distance between adjacent gas stations, is minimized.java

Return the smallest possible value of D.python

Example:函数

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

Note:post

  1. stations.length will be an integer in range [10, 2000].
  2. stations[i] will be an integer in range [0, 10^8].
  3. K will be an integer in range [1, 10^6].
  4. 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使得最大间隔最小的惟一办法是均分。url

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

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

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

解法:二分法,断定条件不是简单的大小关系,而是根据子函数。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 题目汇总