Medium

题目描述

给你一个数组 time ，其中 time[i] 表示第 i 辆公共汽车完成一趟旅途所需要花费的时间。

每辆公共汽车可以 连续 完成多趟旅途，也就是说，一辆公共汽车当前旅途结束后，可以 立即 开始下一趟旅途。每辆公共汽车 独立 运行，也就是说可以同时有多辆公共汽车在运行且互不影响。

给你一个整数 totalTrips ，表示所有公共汽车 总共 需要完成的旅途数目。请返回完成 至少 totalTrips 趟旅途需要花费的 最少 时间。

示例 1：

输入：time = [1,2,3], totalTrips = 5
输出：3
解释：
- 时刻 t = 1 ，每辆公共汽车完成的旅途数分别为 [1,0,0] 。
  已完成的总旅途数为 1 + 0 + 0 = 1 。
- 时刻 t = 2 ，每辆公共汽车完成的旅途数分别为 [2,1,0] 。
  已完成的总旅途数为 2 + 1 + 0 = 3 。
- 时刻 t = 3 ，每辆公共汽车完成的旅途数分别为 [3,1,1] 。
  已完成的总旅途数为 3 + 1 + 1 = 5 。
所以完成至少 5 趟旅途的最少时间为 3 。

示例 2：

输入：time = [2], totalTrips = 1
输出：2
解释：
只有一辆公共汽车，它将在时刻 t = 2 完成第一趟旅途。
所以完成 1 趟旅途的最少时间为 2 。

提示：

  • 1 <= time.length <= 10^5
  • 1 <= time[i], totalTrips <= 10^7

解题思路

这是一道经典的二分搜索问题。核心思想是利用时间的单调性：给定的时间越长，完成的旅途数越多。

分析过程：

  1. 问题转化：我们需要找到最小的时间 t，使得在时间 t 内所有公交车能完成至少 totalTrips 趟旅途。

  2. 关键观察：对于给定时间 t，第 i 辆公交车能完成的旅途数为 ⌊t / time[i]⌋。所有公交车的总旅途数为所有公交车各自完成旅途数的和。

  3. 二分搜索范围：

    • 下界：1（至少需要1个时间单位）
    • 上界：min(time) * totalTrips（最快的公交车完成所有旅途所需时间）

  4. 判断条件：给定时间 mid，计算所有公交车能完成的总旅途数，如果 ≥ totalTrips，说明时间充足，可以尝试更小的时间；否则需要更多时间。

算法步骤：

  • 设置二分搜索的左右边界
  • 在每次迭代中，计算中间时间点所有公交车能完成的总旅途数
  • 根据是否满足条件调整搜索范围
  • 返回满足条件的最小时间

时间复杂度为 O(n log(min(time) × totalTrips))，空间复杂度为 O(1)。

代码实现

class Solution {
public:
    long long minimumTime(vector<int>& time, int totalTrips) {
        long long left = 1;
        long long right = (long long)*min_element(time.begin(), time.end()) * totalTrips;
        
        while (left < right) {
            long long mid = left + (right - left) / 2;
            long long trips = 0;
            
            for (int t : time) {
                trips += mid / t;
            }
            
            if (trips >= totalTrips) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
};

class Solution:
    def minimumTime(self, time: List[int], totalTrips: int) -> int:
        left, right = 1, min(time) * totalTrips
        
        while left < right:
            mid = (left + right) // 2
            trips = sum(mid // t for t in time)
            
            if trips >= totalTrips:
                right = mid
            else:
                left = mid + 1
                
        return left

public class Solution {
    public long MinimumTime(int[] time, int totalTrips) {
        long left = 1;
        long right = (long)time.Min() * totalTrips;
        
        while (left < right) {
            long mid = left + (right - left) / 2;
            long trips = 0;
            
            foreach (int t in time) {
                trips += mid / t;
            }
            
            if (trips >= totalTrips) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
}

/**
 * @param {number[]} time
 * @param {number} totalTrips
 * @return {number}
 */
var minimumTime = function(time, totalTrips) {
    let left = 1;
    let right = Math.min(...time) * totalTrips;
    
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        let trips = 0;
        
        for (const t of time) {
            trips += Math.floor(mid / t);
        }
        
        if (trips >= totalTrips) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n × log(min(time) × totalTrips))
空间复杂度O(1)

其中 n 是公交车的数量，二分搜索的范围是 [1, min(time) × totalTrips]，每次检查需要遍历所有公交车。

相关题目