难度: Hard
Submission
运行时间: 196 ms
内存: 16.3 MB
class Solution:
def minmaxGasDist(self, stations: List[int], k: int) -> float:
n = len(stations)
dist = []
for i in range(1, n):
dist.append(stations[i]-stations[i-1])
l, r = 0, max(dist)
while r - l > 1e-6:
mid = (r + l)/2
need = k
for d in dist:
need -= math.ceil(d/mid) - 1
if need < 0:
l = mid
break
if need >= 0:
r = mid
return l
Explain
此题解采用二分查找法来寻找最大距离的最小值。首先，计算相邻加油站之间的距离并存储在列表dist中。然后，使用二分查找法在区间[0, max(dist)]中寻找最大距离的最小值。在每次迭代中，计算中点mid，并计算如果每个区间最多分成长度为mid的小区间，需要增加的加油站数量need。如果need小于等于k，说明可以在使最大距离不超过mid的情况下增加k个加油站，因此将搜索区间缩小到[l, mid]。否则，将搜索区间缩小到[mid, r]。重复这个过程直到搜索区间足够小。
时间复杂度: O(nlog(max(dist)/1e-6))
空间复杂度: O(n)
class Solution:
def minmaxGasDist(self, stations: List[int], k: int) -> float:
n = len(stations)
dist = [] # 存储相邻加油站之间的距离
for i in range(1, n):
dist.append(stations[i]-stations[i-1])
l, r = 0, max(dist)
while r - l > 1e-6: # 二分查找的终止条件
mid = (r + l)/2
need = k
for d in dist:
need -= math.ceil(d/mid) - 1 # 计算每个区间需要增加的加油站数量
if need < 0:
l = mid
break
if need >= 0:
r = mid
return l
Explore
在二分查找中选择`1e-6`作为终止条件是为了确保结果的精度足够高，同时避免无限循环。此精度通常是基于问题的实际需求和实际应用场景决定的。在加油站问题中，差异小于`1e-6`的最大距离在实际情况中几乎没有区别，因此这样的精度是合理的。此外，考虑到浮点运算的误差，`1e-6`提供了一个平衡计算效率和结果精度的有效方法。
在函数`math.ceil(d/mid) - 1`中，`math.ceil(d/mid)`计算的是将距离`d`完全覆盖所需的加油站数量，包括起点的加油站。由于每个区间的起点已经有一个加油站（除了第一个外，每个加油站是上一个区间的终点），所以需要将计算出的加油站数量减1，以得到真正需要新建的加油站数量。
在二分查找过程中，如果`need`变量一直小于0，这表明在当前的`mid`值下，预设的加油站数量`k`过多，即使在最大距离较大的情况下也足够使用。这导致二分查找会调整`mid`值，增大它以寻找一个更紧凑的最大距离。这样的调整有助于我们找到一个尽可能小的最大距离，同时仍能满足不超过`k`个加油站的条件。
在二分查找过程中，通过不断调整搜索区间[l, r]，逐渐将可能的最大距离范围缩小到一个非常小的区间（即`l`和`r`非常接近时停止），可以确保找到最小的可接受最大距离。每次迭代都基于`need`的计算结果来决定是缩小还是增大`mid`，确保如果`need >= 0`，则可能的最大距离`mid`是足够的，否则需要增加`mid`。最终，当`l`和`r`足够接近时，我们得到的`l`（或`r`）就是可以接受的最小最大距离。