完成旅途的最少时间
难度:
标签:
题目描述
代码结果
运行时间: 577 ms, 内存: 29.1 MB
/*
题目思路:
同样使用二分查找的方法,但使用 Java Stream 进行实现。我们通过对所有公交车的行程时间计算他们在当前时间段内的完成旅途总数,并用这个总数与 totalTrips 比较,从而确定最少时间。*/
import java.util.Arrays;
public class MinimumTimeStream {
public static long minimumTime(int[] time, int totalTrips) {
long left = 1, right = (long) 1e14;
while (left < right) {
long mid = (left + right) / 2;
long trips = Arrays.stream(time).mapToLong(t -> mid / t).sum();
if (trips >= totalTrips) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
解释
方法:
这道题的核心思路是使用二分查找来确定最少时间完成所有旅途。首先确定搜索的时间范围:最小时间left设为1(最快可能的时间),最大时间right设为min(time) * totalTrips(假设所有旅途都由最快的公交车完成)。在这个搜索范围内,我们计算中间时间点mid,然后计算所有公交车在mid时间内可以完成的旅途总数s。如果s小于totalTrips,意味着mid太小,需要增加时间,因此调整left为mid + 1;如果s大于等于totalTrips,说明可能有解或者可以有更小的解,调整right为mid - 1。当left超过right时,left就是最少需要的时间。
时间复杂度:
O(n log(min(time) * totalTrips))
空间复杂度:
O(1)
代码细节讲解
🦆
为什么选择二分查找作为解决这个问题的方法?
▷