[1870] 准时到达的列车最小时速

details

解题思路：

这道题可以使用二分查找来解决，因为随着时速的增加，完成所有路程所需的时间会单调递减。我们可以利用这个单调性，二分搜索最小的速度。

1. 目标函数：对于给定的速度 v，我们可以计算总的行驶时间。如果总时间不超过 hour，则 v 是可行的速度，否则不可行。
2. 二分搜索：从速度 1 开始，不断尝试更大的速度，直到找到最小的可行速度。

代码实现（JavaScript）：

/**
 * @param {number[]} dist
 * @param {number} hour
 * @return {number}
 */
var minSpeedOnTime = function (dist, hour) {
    const n = dist.length;

    // 判断是否可以用给定速度 speed 在 hour 时间内到达
    const canArriveOnTime = speed => {
        let time = 0;
        for (let i = 0; i < n - 1; i++) {
            time += Math.ceil(dist[i] / speed); // 前 n-1 段需要向上取整
        }
        time += dist[n - 1] / speed; // 最后一段无需取整
        return time <= hour;
    };

    let left = 1,
        right = 10e7;
    let result = -1;

    while (left <= right) {
        const mid = ((left + right) / 2) >> 0;
        if (canArriveOnTime(mid)) {
            result = mid; // mid 是可行解，尝试更小速度
            right = mid - 1;
        } else {
            left = mid + 1; // mid 速度不够，增加速度
        }
    }

    return result;
};

复杂度分析：

• 时间复杂度: O(n * log(maxSpeed))，其中 n 是 dist 数组的长度，maxSpeed 是最大速度上限。我们在每次二分时，需要遍历一遍 dist 来计算总时间，二分的次数是 log(maxSpeed)。
• 空间复杂度: O(1)，只使用了常数额外空间。