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

774. Minimize Max Distance to Gas Station

题目地址

https://leetcode.com/problems/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.

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[0][i] = deltas[0] / (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];
  }
}

Approach #2 Binary Search

class Solution {
  public double minmaxGasDist(int[] stations, int K) {
        int count;
    int N = stations.length;
    double left = 0;
    double right = stations[N-1] - stations[0];
    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[0]/a[1] < b[0]/b[1]) ? 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[1];
    pq.add(cur);
  }
  double[] value =  pq.poll();
  return value[0] / value[1];
}