题目描述

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

题解

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length; // 获取加油站的数量
        int i = 0; // 从第 0 个加油站开始尝试

        while (i < n) { // 外层循环，遍历每个可能的起点
            int sumOfGas = 0, sumOfCost = 0; // 初始化总油量和总消耗量
            int cnt = 0; // 计数器，记录走过的加油站数量

            while (cnt < n) { // 内层循环，尝试从当前起点出发，走一圈
                int j = (i + cnt) % n; // 计算当前加油站的索引
                sumOfGas += gas[j]; // 累加当前加油站的油量
                sumOfCost += cost[j]; // 累加从当前加油站到下一个加油站的油耗

                if (sumOfCost > sumOfGas) { // 如果油耗超过了油量，无法继续
                    break; // 退出内层循环
                }
                cnt++; // 成功经过一个加油站
            }

            if (cnt == n) { // 如果成功经过了所有的加油站，返回起点
                return i;
            } else {
                i = i + cnt + 1; // 如果失败，从下一个加油站开始继续尝试
            }
        }

        return -1; // 如果没有找到合适的起点，返回 -1
    }
}