加油站

    数组 贪心

    题目描述

    在一条环路上有 n 个加油站，第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从某一个加油站出发，开始时油箱为空。

    返回出发加油站的编号，使你能够绕环路行驶一圈；如果不存在这样的出发点，则返回 -1。

    要求：

    • 如果存在解，则保证它是唯一的。

    思路分析

    朴素的做法是枚举每一个起点，然后模拟行驶一圈，时间复杂度为 O(n^2)，不够高效。

    更优的做法是利用贪心：

    全局判断：所有站点净油量 gas[i] - cost[i] 之和，反映了能否完成整圈行驶。如果总净油量 < 0，说明任意起点都无法完成环路，直接返回 -1。

    局部贪心：否则，一定存在唯一解，贪心找到起点：

    • 从第 0 站开始遍历，维护一个 currentTank（当前从候选起点出发的剩余油量）。
    • 每到一站，累加该站的净油量。
    • 一旦 currentTank < 0，说明从当前候选起点出发，无法走到这里，起点向后移一位，同时重置 currentTank。
    • 遍历结束后，gasStationIndex 就是答案。

    贪心正确性：当 currentTank 变负时，可以证明候选起点到当前站点之间的任何站都不可能是有效起点，因此直接跳过它们，将起点移到下一站。

    算法步骤

    1. 初始化 gasStationIndex = 0、totalTank = 0、currentTank = 0。
    2. 遍历每个站点，计算净油量 netGas = gas[i] - cost[i]。
    3. 将 netGas 同时累加到 totalTank 和 currentTank。
    4. 若 currentTank < 0，将 gasStationIndex 移到 i + 1，并重置 currentTank = 0。
    5. 遍历结束后，若 totalTank >= 0 返回 gasStationIndex，否则返回 -1。

    示例代码

    /**
 * 贪心算法：找出能够绕环路行驶一圈的起始加油站下标。
 *
 * 核心思路：
 * 1. 如果所有站点的净油量之和 < 0，说明全局无解，直接返回 -1。
 * 2. 否则，一定存在唯一解。用贪心策略寻找起点：
 *    - 从头遍历，累加当前净油量；
 *    - 一旦当前油箱变负，说明从当前起点出发无法到达这里，
 *      将起点候选移到下一站，并重置当前油箱。
 *
 * @param gas  每个加油站可加的油量
 * @param cost 从每个加油站到下一站所需的油量
 * @returns    能完成环路的起始站下标，无解则返回 -1
 */
export function canCompleteCircuit(gas: number[], cost: number[]): number {
    // 记录当前候选起始站的下标
    let gasStationIndex = 0;
    // 记录所有站点净油量的总和，用于判断全局是否有解
    let totalTank = 0;
    // 记录从候选起点出发到当前站点的剩余油量
    let currentTank = 0;

    for (let i = 0; i < gas.length; i++) {
        // 当前站点的净油量：加的油减去到下一站的消耗
        const netGas = gas[i] - cost[i];
        // 累加到全局总量，最终用于判断有无解
        totalTank += netGas;
        // 累加到当前路段油量，模拟从候选起点出发的行驶状态
        currentTank += netGas;

        if (currentTank < 0) {
            // 油箱变负，说明从当前候选起点出发无法到达站点 i
            // 将起点候选移到 i+1，从那里重新出发
            gasStationIndex = i + 1;
            // 重置当前油箱，相当于从新起点重新计算
            currentTank = 0;
        }
    }

    // 如果全局总净油量 >= 0，则一定有解，返回贪心找到的起点；否则无解
    return totalTank >= 0 ? gasStationIndex : -1;
}

    复杂度分析

    • 时间复杂度：O(n)，其中 n 是加油站数量。只需一次线性遍历。
    • 空间复杂度：O(1)。只用到常数个额外变量。

    示例演示

    以 gas = [1, 2, 3, 4, 5]、cost = [3, 4, 5, 1, 2] 为例：

    每个站点的净油量：

    站点 (i)gas[i]cost[i]netGas
    013-2
    124-2
    235-2
    341+3
    452+3

    遍历过程：

    站点 (i)netGastotalTankcurrentTankgasStationIndex
    0-2-2-21（重置）
    1-2-4-22（重置）
    2-2-6-23（重置）
    3+3-333
    4+3063

    遍历结束，totalTank = 0 >= 0，返回 gasStationIndex = 3。

    验证：从站点 3 出发，依次经过 3 → 4 → 0 → 1 → 2，油箱始终非负，可完成环路。