题解 | #加油站#

题目的主要信息：

在一条环路上有 n 个加油站，其中第 i 个加油站有 gas[i] 升油，假设汽车油箱容量无限，从第 i 个加油站驶往第 (i+1)%n 个加油站需要花费 cost[i] 升油。

请问能否绕环路行驶一周，如果可以则返回出发的加油站编号，如果不能，则返回 -1。 题目数据可以保证最多有一个答案。

方法一：

暴力法。遍历所有可能的起点，判断以i为起点是否能够行驶一周，判断的方法是，每到一个加油站就计算当前油箱的剩余量，如果油箱剩余量已经小于零，则表示以i为起点无法绕行一周。如果在行驶过程中没有出现油量小于零的情况，表示成功绕行一周。

具体做法：

class Solution {
public:
    int gasStation(vector<int>& gas, vector<int>& cost) {
        int current = 0;
        int n = gas.size();
        for (int i = 0; i < gas.size(); ++i) {//遍历所有可能的起点
            current = 0;
            int flag = 1;
            for (int j = 0; j < cost.size(); j++) {//以i为起点，判断是否能行驶一周
                current += gas[(i + j)%n] - cost[(i+j)%n];//每到一个加油站计算目前油箱剩余量
                if(current < 0) {//如果油箱剩余量小于0，则无法绕行一周
                    flag = 0;
                    break;
                }
            }
            if (flag) {//如果flag=1表示可以绕行一周
                return i;
            }
        }
        return -1;
       
    }
};

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，双重for循环。
• 空间复杂度：$O(1)O(1)$，只用了常数空间。

方法二：

如果存在加油站使得从这个加油站出发可以绕行一周的话，那么遍历一遍gas数组和cost数组，${\sum }_i^{n}gas[i]-cost[i]\backslash sum\; \_i^ngas[i]-cost[i]$的结果应该大于等于0，且到达每个站点的油量不会小于0。根据这个思想，可以优化方法一，只需要遍历一遍所有站点，current记录当前剩余油量，sum计算${\sum }_i^{n}gas[i]-cost[i]\backslash sum\; \_i^ngas[i]-cost[i]$，在遍历的过程中如果出现current小于零，则更换起始站点。遍历结束后，如果sum大于等于0，说明可以绕行一周。

具体做法：

class Solution {
public:
    int gasStation(vector<int>& gas, vector<int>& cost) {
        int start = 0;//初始起点
        int sum = 0;
        int current = 0;
        for (int i = 0; i < gas.size(); ++i) {//遍历所有站点
            current += (gas[i] - cost[i]);//目前剩余的油量
            sum += (gas[i] - cost[i]);
            if (current < 0) {//当前剩余油量小于0，更换起始站点
                start = i + 1;
                current = 0;//重置剩余油量
            }
        }
        if (sum >= 0) {//如果剩余油量大于0，说明可以绕行一周
            return start;//能够成功绕行一周的起始站点
        } else {//油量小于0，不可能绕行一周
            return -1;
        }
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，遍历所有站点。
• 空间复杂度：$O(1)O(1)$，只用了常数空间。