加油站[中等]

优质博文：IT-BLOG-CN

一、题目

在一条环路上有n个加油站，其中第i个加油站有汽油gas[i]升。你有一辆油箱容量无限的的汽车，从第i个加油站开往第i+1个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。给定两个整数数组gas和cost，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回-1。如果存在解，则保证它是唯一的。

示例 1:
输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从3号加油站(索引为3处)出发，可获得4升汽油。此时油箱有= 0 + 4 = 4升汽油
开往4号加油站，此时油箱有4 - 1 + 5 = 8升汽油
开往0号加油站，此时油箱有8 - 2 + 1 = 7升汽油
开往1号加油站，此时油箱有7 - 3 + 2 = 6升汽油
开往2号加油站，此时油箱有6 - 4 + 3 = 5升汽油
开往3号加油站，你需要消耗5升汽油，正好足够你返回到3号加油站。
因此，3可为起始索引。

示例 2:
输入:gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从0号或1号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从2号加油站出发，可以获得4升汽油。 此时油箱有= 0 + 4 = 4升汽油
开往0号加油站，此时油箱有4 - 3 + 2 = 3升汽油
开往1号加油站，此时油箱有3 - 3 + 3 = 3升汽油
你无法返回2号加油站，因为返程需要消耗4升汽油，但是你的油箱只有3升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。

gas.length == n
cost.length == n
1 <= n <= 105
0 <= gas[i], cost[i] <= 104

二、代码

遍历： 从头到尾遍历每个加油站，并检查以该加油站为起点，最终能否行驶一周。我们可以通过减小被检查的加油站数目，来降低总的时间复杂度。如何减少被检查的加油站呢？我们可以从第一个加油站开始判断是否可以走完所有的加油站，如果到第x的时候，发现不能走完，此时不是从第1个加油站判断是否可以走完整个加油站，而是从第x+1的加油站开始判断，这样就可以通过一次遍历，完成整个计算。

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int len = gas.length; // 外层我只遍历一次即可
        int i = 0;
        while (i < len) {
            // 每次进来都是重新判断是否可以走完全程，所以总的加油和耗油都是0
            int sumGas = 0, sumCost = 0;
            int count = 0;
            // 确定子循环的次数
            while (count < len) {
                // i是变化的，所以我们要去摸获取下标
                int cur = (i + count) % len ;
                // 判断加油是否大于耗油
                sumCost += cost[cur];
                sumGas += gas[cur];
                if (sumCost > sumGas) {
                    break;
                }
                count++;
            }

            // 当 count == len 的时候表示循环完毕，i就是符合条件的
            if (count == len) {
                return i;
            }
            i = i + count + 1;
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

时间复杂度： O(N)，其中N为数组的长度。我们对数组进行了单次遍历。
空间复杂度： O(1)。