在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。 给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。 来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/gas-station 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

首先，我们可以想到暴力枚举所有可能的起点，对于每个起点再模拟一遍行驶过程，判断是否能够回到起点。但是这样的时间复杂度为 $O(n^2)$，显然会超时。

观察题目，我们会发现，如果从某个加油站出发不能走完一圈，那么这个加油站到任何一个加油站都不能走完一圈。因此，我们可以利用这个性质，从头开始遍历每个加油站，假设当前遍历到的加油站是 $i$，如果从 $i$ 出发不能走完一圈，那么就从 $i+1$ 开始重新遍历。

具体来说，我们用变量 $start$ 记录起点，$total$ 记录当前油量，$remain$ 记录从 $start$ 出发，到当前加油站剩余的油量。如果 $remain < 0$，意味着从 $start$ 出发到当前加油站都不可能走完一圈，因此将起点设为 $i+1$，同时将 $total$ 和 $remain$ 重新置为 $0$。最后，如果 $total$ 大于等于 $0$，说明可以走完一圈，返回起点 $start$，否则返回 $-1$。

时间复杂度：$O(n)$

Python 代码：

相关问题

用c语言写代码：在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。 如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

以下是用C语言实现的代码：

int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize){
    int totalGas = 0, currGas = 0, start = 0;
    for(int i = 0; i < gasSize; i++){
        totalGas += gas[i] - cost[i];
        currGas += gas[i] - cost[i];
        if(currGas < 0){ // 无法到达下一个加油站
            currGas = 0;
            start = i + 1;
        }
    }
    return (totalGas >= 0) ? start : -1; // 如果总油量 >= 总消耗量，一定可以完成绕环路行驶一周
}

思路解析：

- 定义变量 `totalGas` 表示总油量与总消耗量之差。
- 定义变量 `currGas` 表示当前油量与当前消耗量之差。
- 定义变量 `start` 表示起点加油站的下标。
- 遍历所有的加油站，将油量和消耗量的差累加到 `totalGas` 和 `currGas` 中。
- 如果 `currGas` 小于 0，表示无法到达下一个加油站，则将 `currGas` 重置为 0，并将起点加油站的下标设置为当前加油站的下一个位置。
- 最后判断 `totalGas` 是否大于等于 0，如果是，则一定可以完成绕环路行驶一周，返回起点加油站的下标，否则返回 -1。

用C语言并根据贪心算法编写代码:在一条环路上有N个加油站,其中第i个加油站有汽油gas[i]升.你有一辆油箱容量无限的汽车,从第i个建有站开往第i+1个加油站需要汽油cost[i]升.你从其中的一个加油站出发,开始时油箱为空.如果你可以绕环路行使一周,则返回出发时加油站的编号,否则返回-1.

以下是基于贪心算法的 C 语言代码实现：

#include <stdio.h>

int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize){
    int start = 0;  // 起点
    int totalGas = 0;  // 总油量
    int currGas = 0;  // 当前油量
    
    for (int i = 0; i < gasSize; i++) {
        totalGas += gas[i] - cost[i];  // 计算总油量
        currGas += gas[i] - cost[i];  // 计算当前油量
        if (currGas < 0) {  // 当前油量不足以到达下一个加油站
            start = i + 1;  // 将起点设置为下一个加油站
            currGas = 0;  // 当前油量清零
        }
    }
    
    return totalGas >= 0 ? start : -1;  // 如果总油量大于等于0，则可以绕环路行使一周，返回起点，否则返回-1
}

int main() {
    int gas[] = {1, 2, 3, 4, 5};
    int cost[] = {3, 4, 5, 1, 2};
    int result = canCompleteCircuit(gas, 5, cost, 5);
    printf("Result: %d\n", result);
    return 0;
}

该算法的时间复杂度为 O(n)，其中 n 为加油站数量。