Massive Algorithms: LeetCode 774 - Minimize Max Distance to Gas Station

LeetCode 774 - Minimize Max Distance to Gas Station

https://blog.csdn.net/magicbean2/article/details/79663323
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.

X.
http://www.cnblogs.com/grandyang/p/8970057.html

这道题说给了我们n个加油站，两两之间相距不同的距离，然后我们可以在任意地方新加K个加油站，问能使得任意两个加油站之间的最大距离的最小值是多少。乍眼一看，感觉很绕，一会儿最大，一会儿最小的。其实我们可以换个场景，比如n个人站一队，每两个人之间距离不同，有的人之间距离可能很大，有的人可能挨得很近。我们现在需要再加入K个人到队列中，我们希望人与人之间的距离尽可能小，所以新人就应该加入到距离大的地方，然后问我们加入K个人后，求人与人之间的最大距离。这么一说，是不是清晰一点了呢。博主最开始看到这个加油站的题，以为跟之前那道Gas Station有关联，结果发现二者并没有什么关系，只不过公用了加油站这个场景而已。对于这道题，我们还是抽离出本质，就是数组插数问题。博主最先考虑的是用贪婪算法，就是先算出每两个数字之间的距离，然后我们每次往距离最大的那两个数字之间插入一个数字，这种想法看似正确，但是会跪在这样一个test case：

[10, 19, 25, 27, 56, 63, 70, 87, 96, 97]，K = 3

其两两之间的距离为：

9，6，2，29，7，7，17，9，1

如果按照博主前面所说的方法，会先将29分开，变成两个14.5，然后会将17分开，变成两个8.5，还剩一个加油站，会将其中一个14.5分开，变成两个7.25。但是这样弄下来，最大的距离还是14.5，而实际上我们有更好的办法，我们用两个加油站将29三等分，会变成三个9.67，然后用剩下的一个去分17，得到两个8.5，此时最大距离就变成了9.67，这才是最优的解法。这说明了博主那种图样图森破的贪婪算法并不work，缺乏对Hard题目的尊重。

后来看了官方解答贴中的解法，发现用DP会内存超标MLE，用堆会时间超标TLE。其实这道题的正确解法是用二分搜索法，博主第一反应是，还有这种操作！！？？就是有这种操作！！！这道题使用的二分搜索法是博主归纳总结帖LeetCode Binary Search Summary 二分搜索法小结中的第四种，即二分法的判定条件不是简单的大小关系，而是可以抽离出子函数的情况，下面我们来看具体怎么弄。如果光说要用二分法来做，那么首先就要明确的是二分法用来查找什么，难道是用来查找要插入加油站的位置吗？很显然不是，其实是用来查找那个最小的任意两个加油站间的最大距离。这其实跟之前那道Kth Smallest Element in a Sorted Matrix非常的类似，那道题的二分搜索也是直接去折半定位所求的数，然后再来验证其是否真的符合题意。这道题也是类似的思路，题目中给了数字的范围[0, 10^8]，那么二分查找的左右边界值就有了，又给了误差范围10^-6，那么只要right和left差值大于这个阈值，就继续循环。我们折半计算出来的mid就是一个candidate，我们要去验证个candidate是否符合题意。验证的方法其实也不难，我们计算每两个加油站之间的距离，如果此距离大于candidate，则计数器累加1，如果大于candidate距离的个数小于等于k，则说明我们的candidate偏大了，那么right赋值为mid；反之若大于candidate距离的个数大于k，则说明我们的candidate偏小了，那么left赋值为mid。最后left和right都会收敛为所要求的最小的任意两个加油站间的最大距离，是不是很神奇呀

http://hehejun.blogspot.com/2018/02/leetcodeminimize-max-distance-to-gas.html

和Split Array Largest Sum一样，此题也有binary search的解法。因为，我们确定目标答案target在区间(0, max(stations[i] - stations[i - 1])]中，并且给定y，我们可以在O(n)的时间里确定其是否为target的上/下界：

假设区间长len，让区间满足子区间的最大值不超过y需要的额外加油站的数目为ceil(len / y)，那么我们只需要算出满足y的条件下需要的加油站的总数sum，如果sum <= k，代表我们还可以用更多的加油站让最大区间更小，所以y是target的上界，target <= y
如果sum > k，代表我们需要减少额外的加油站，这样y是target的上界，target >= y

注意上下界都是double类型，我们设定误差的范围e，当上下界误差小于e的话我们终止即可。时间复杂度O(n * log(max(stations[i] - stations[i - 1])))，代码如下：

https://www.jiuzhang.com/solution/minimize-max-distance-to-gas-station/
二分"最大距离", 对每个 mid 统计可以添加的最少的加油站, 如果 > k 说明 mid 太小需要增大 (增大 mid 才可能添加更少的加油站)

    public double minmaxGasDist(int[] stations, int k) {
        // Write your code here
        double start = 0, end = stations[stations.length - 1] - stations[0];
        double eps = 1e-6;
        
        while (start + eps < end) {
            double mid = (start + end) / 2;
            int count = checkStations(stations, mid);
            if (count > k) {
                // minimum stations added is > K
                // so we nned to increase the mid
                start = mid;
            } else {
                // minimum stations added is <= K
                // so we need to narrow the mid
                end = mid;
            }
        }
        return start;
    }
    
    // get the minimum stations count at max distance 'dist'
    private int checkStations(int[] stations, double dist) {
        int count = 0;
        for (int i = 1; i < stations.length; i++) {
            count += (int) ((stations[i] - stations[i - 1]) / dist);
            // for example, 10 / 3, at least put 3 stations
            // to satisfy the condition: max distance is 'dist'
        }
        return count;
    }
1

https://www.acwing.com/solution/leetcode/content/220/

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

double s = 0, e = 10e9;

while (e - s > 1e-8) {

double mid = (s + e) / 2;

if (checkMin(stations, mid, K) < 0)

s = mid;

else

e = mid;

}

return s;

}

private int checkMin(int[] stations, double dist, int k) {

for (int i = 1; i < stations.length; i++) {

double gap = (double) (stations[i] - stations[i - 1]);

if (gap > dist) {

k -= (int) (gap / dist);

if (gap % dist == 0)

k--;

}

return k;

}

https://chenboxie.wordpress.com/2018/06/24/leetcode-774-minimize-max-distance-to-gas-station/

I -- Construct a candidate solution

To construct a candidate solution, we need to understand first what the desired solution is. The problem description requires we output the minimum value of the maximum distance between adjacent gas stations. This value is nothing more than a non-negative double value, since the distance between any adjacent stations cannot be negative and in general it should be of double type. Therefore our candidate solution should also be a non-negative double value.

II -- Search space formed by all the candidate solutions

Let max be the maximum value of the distances between any adjacent stations without adding those additional stations, then our desired solution should lie within the range [0, max]. This is because adding extra stations (and placing them at proper positions) can only reduce the maximum distance between any adjacent stations. Therefore our search space will be [0, max] (or the upper bound should be at least max).

III -- Verify a given candidate solution

This is the key part of this trial and error algorithm. So given a candidate double value d, how do we determine if it can be the minimum value of the maximum distance between any adjacent stations after adding K extra stations? The answer is by counting.

If d can be the minimum value of the maximum distance between any adjacent stations after adding K extra stations, then the following two conditions should be true at the same time:

The total number of stations we can add between all adjacent stations cannot go beyond K. In other words, assume we added cnt_i stations in between the pair of adjacent stations (i, i+1), then we should have sum(cnt_i) <= K.
For each pair of adjacent stations (i, i+1), the minimum value of the maximum distance between adjacent stations after adding cnt_i additional stations cannot go beyond d. If the original distance between station i and i+1 is d_i = stations[i+1] - stations[i], then after adding cnt_i additional stations, the minimum value of maximum distance between any adjacent stations we can obtain is d_i / (cnt_i + 1), which is achieved by placing those stations evenly in between stations i and i+1. Therefore we require: d_i / (cnt_i + 1) <= d, which is equivalent to cnt_i >= (d_i/d - 1).

So you can see that the two conditions are actually “contradictory” to each other: to meet condition 1, we want cnt_i to be as small as possible; but to meet condition 2, we’d like it to be as large as possible. So in practice, we can alway choose the set of smallest cnt_i‘s that satisfy the second condition and double check if they also meet the first condition. If they do, then d will set an upper limit on the final minimum value obtainable; otherwise d will set a lower limit on this minimum value.

This verification algorithm runs at O(n), where n is the length of the stations array. This is acceptable if we can walk the search space very efficiently (which can be done at the order of O(log(max/step)), with step = 10^-6). In particular, this is much faster than the straightforward O(Klogn) solution where we add the stations one by one in a greedy manner (i.e., always reduce the current maximum distance first), given that K could be orders of magnitude larger than n (note this greedy algorithm can be optimized to run at O(nlogn), see wannacry89’s post here).

https://blog.csdn.net/u014688145/article/details/79195114
首先求出每个station之间的距离，考虑如下问题：两个station为[1, 9]，gap为8。要插入一个station使得最大的最小，显然插入后应该为[1, 5, 9]，最大间隔为4。举个反例，如果插入后为[1, 6, 9], [1, 3, 9]，它们的最大间隔分别为5， 6，明显不是最小。从这里可以看出，对于插入k个station使得最大的最小的唯一办法是均分。
换个思路，如果我们假设知道了答案会怎么样？因为知道了最大间隔，所以如果目前的两个station之间的gap没有符合最大间隔的约束，那么我们就必须添加新的station来让它们符合最大间隔的约束，这样一来，对于每个gap我们是能够求得需要添加station的个数。如果需求数<=K，说明我们还可以进一步减小最大间隔，直到需求数>K。

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;

}

X. DP
http://hehejun.blogspot.com/2018/02/leetcodeminimize-max-distance-to-gas.html
这道题和Split Array Largest Sum十分类似。首先我们也可以考虑区间DP的解法。对于前i个interval(i + 1个加油站)，我们额外增加j个加油站，相邻加油站间距的最大值为x，那么在在所有可能中x的最小值我们用DP[i][j]表示。我们有递推公式：

dp[i][j] = min(max(dp[i - 1][j - k], (stations[i] - stations[i - 1]) / (k + 1)))
base case: dp[i][0] = max(stations[1] - stations[0], ..., stations[i] - stations[i - 1])

公式中的(stations[i] - stations[i - 1]) / (k + 1)可以这么理解: 把一个interval用k个节点分为k + 1的子区间，那么minimize子区间最大值的方法就是吧interval等分。假设输入为n个加油站的位置，我们额外增加k个，算法时间复杂度和空间复杂度均为O(n * k)。代码如下：

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

int len = stations.size();

//dp[i][j] represnets minimum max distance when adding j new gas stations to first i intervals

//dp[i][j] = min(max(dp[i - 1][j - k], (stations[i] - stations[i - 1]) / (k + 1)))

//base case: dp[i][0] = max(stations[0], ..., stations[i - 1]), dp[0][j] = 0

vector<vector<double>> dp(len, vector<double>(K + 1, 0));

for (int i = 1; i < len; ++i)dp[i][0] = max(dp[i - 1][0], static_cast<double>(stations[i] - stations[i - 1]));

for (int i = 1; i < len; ++i)

{

for (int j = 1; j <= K; ++j)

{

dp[i][j] = numeric_limits<double>::max();

for (int k = 0; k <= j; ++k)

{

dp[i][j] = min(max(dp[i - 1][j - k], (stations[i] - stations[i - 1]) / (k + 1.0)), dp[i][j]);

}

return dp[len - 1][K];

}

首先要从离散的点抽象出Interval的概念，其实已有的gas station就是一个个Interval。更为关键的是，这些interval可以视为永远不变，唯一变化的就是他们里边可能插入多少个K。基于这些interval，我们每次选择插入K的时候，只要选择插入当前所有interval中dist最大的那个，一直插入直到它比第二大小为止。插完所有的K，我们就得到了最后的解。

有了以上的理解，一个priority_queue就可以轻易的解决问题，用addK()去update当前interval里的value，然后把update完的top重新插回priority_queue。解法复杂度为O(klogn)

http://fyou.me/blog/2018/05/09/minimize-max-distance-to-gas-station/

这题的难点在于正确理解题意并抽象化后找出算法，关键点在于：

由于最早给定的gas station，随着K的插入，变化的并不是interval，而是每个interval内部的dist。

只关注最后的最大距离，并不关心每个gas station插在了哪里。

struct Interval {

int length, k, dist;

Interval(int i) : length(i), k(1), dist(i) {}

bool operator< (const Interval& other) const {

return dist < other.dist;

}

void addK() {

k++;

dist = length/k;

}

};

priority_queue<Interval> buildQueue(const vector<int>& v) {

vector<int> ret(v.size());

adjacent_difference(v.begin(), v.end(), ret.begin());

ret.erase(ret.begin());

return priority_queue<Interval>(ret.begin(), ret.end());

}

int minMaxDist(const vector<int>& v, int k) {

auto pq = buildQueue(v);

int maxDist = (v.back() - v.front())/(k+1); // just for optimization

while(k) {

Interval top = pq.top();

pq.pop();

while(pq.top() < top || top.dist > maxDist) {

top.addK();

k--;

}

pq.push(top);

}

return pq.top().dist;

}

有了以上的理解，一个priority_queue就可以轻易的解决问题，用addK()去update当前interval里的value，然后把update完的top重新插回priority_queue。解法复杂度为O(klo

1、采用优先队列：采用优先队列的思路比较简单：就是每次找出gap最大的一个区间，然后新加入一个station，直到所有的k个station都被加入，此时最大的gap即为所求。在实现上我们采用优先队列，使得每次最大的gap总是出现在队首。这种方法的空间复杂度是O(n)，时间复杂度是O(klogn)，其中k是要加入的新station的个数，n是原有的station个数。这种方法应该没毛病，但是还是没有通过所有的数据测试。
double minmaxGasDist(vector<int>& stations, int K) {
priority_queue<vector<double>> pq; // {avg_distance, count}
for (int i = 0; i + 1 < stations.size(); ++i) {
pq.push({stations[i + 1] - stations[i], 1});
}
for (int i = 0; i < K; ++i) {
vector<double> vec = pq.top();
pq.pop();
vec[0] = vec[0] * vec[1] / (vec[1] + 1);
vec[1] += 1.0;
pq.push(vec);
}
return pq.top()[0];
}

LeetCode 774 - Minimize Max Distance to Gas Station

Labels

Popular Posts