[LeetCode]Minimize Max Distance to Gas Station

这道题和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)。代码如下：

和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])))，代码如下：