leetcode
leetcode 1901 ~ 1950
完成旅途的最少时间

完成旅途的最少时间

难度:

标签:

题目描述

代码结果

运行时间: 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)

代码细节讲解

🦆
为什么选择二分查找作为解决这个问题的方法?
二分查找是解决这个问题的有效方法,因为我们寻找的是满足特定条件(即在给定时间内完成所有旅途)的最小时间。这个时间值从理论上是有序的,即如果某个时间点可以完成所有旅途,那么任何比这个时间点长的时间也都可以;反之,比这个时间点短的时间则不能完成所有旅途。这种有序性质使得二分查找成为寻找最优解的理想选择,因为二分查找能够有效地缩小搜索范围,从而快速地找到满足条件的最小时间。此外,考虑到时间范围可能很大,直接遍历每一个可能的时间点会非常耗时,而二分查找的时间复杂度为O(log n),可以大幅提高效率。

相关问题