Comment on page

# 774.Minimize-Max-Distance-to-Gas-Station

## 题目描述

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

## 代码

### Approach #1 Dynamic Programming [Memory Lmit Exceeded]

Time: O(NK^2) && Space: O(NK)
class Solution {
public double minmaxGasDist(int[] stations, int K) {
int N = stations.length;
double[] deltas = new double[N-1];
for (int i = 0; i < N-1; i++) {
deltas[i] = stations[i+1] - stations[i];
}
double[][] dp = new double[N-1][K+1];
for (int i = 0; i <= K; i++)
dp[i] = deltas / (i+1);
for (int p = 1; p < N-1; p++) {
for (int k = 0; k <= K; k++) {
double bns = 999999999;
for (int x = 0; x <= k; x++) {
bns = Math.min(bns, Math.max(deltas[p] / (x+1), dp[p-1][k-x]));
}
dp[p][k] = bns;
}
}
return dp[N-2][K];
}
}
class Solution {
public double minmaxGasDist(int[] stations, int K) {
int count;
int N = stations.length;
double left = 0;
double right = stations[N-1] - stations;
while (right - left > 1e-6) { // left - right < 1e-6 TLE
double mid = (left + right) / 2;
count = 0;
for (int i = 0; i < N-1; i++) {
count += (int)((stations[i+1] - stations[i]) / mid);
}
if (count > K) {
left = mid;
} else {
right = mid;
}
}
return right;
}
}

### Approach #3 PriorityQueue Greedy [Time Limit Exceeded]

public double minmaxGasDist(int[] stations, int K) {
PriorityQueue<double[]> pq = new PriorityQueue<double[]>(
(a,b) -> (a/a < b/b) ? 1 : -1);
for (int i = 1; i < stations.length; ++i) {
pq.add(new double[] {stations[i] - stations[i-1], 1.0});
}
while (K-- > 0) {
double [] cur = pq.poll();
++cur;