问题传送门：https://leetcode.cn/problems/gas-station/description/

常规思路是暴力解法，以每一个点作为起点检索，在路上如果某一个点的油箱容量为负，说明到不了， 直接break到下一个点，直到所有的点都被遍历过。思路是没问题，就是会超时。

C++
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int length = gas.size();
        vector<int> result(length, 0);
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                int index = (i + j) % length;
                result[i] += gas[index] - cost[index];
                if (result[i] < 0) {
                    break;
                }
            }
            if (result[i] >= 0) {
                return i;
            }
        }
        return -1;
    }
};

换一种思维方式：

• 相关变量：total_tank。如果从0到n点，它所有的油箱总所得，和所有的油箱总支出的差值是负数，那么说明油量不能够支持完成环形遍历，需要返回-1。如果为正数，则一定存在符合条件的点。题目另外也规定了该点只有一个。
• 相关变量：curr_tank。这个值用于模拟当前油箱的剩余油量，当它小于0的时候，说明当前的点无法到达。
• 相关变量：start_station。这个值用于记录当前的起点，并与i进行运行模拟。

算法思想是：

1. 初始化各个值，将起点设定为0.
2. total_tank记录总的油量数据。
3. curr_tank用于记录从start_station到i的过程中，油箱油量的变化。如果它变为负数，则证明：从start_station到i-1中的这个区间内的任意一点，都不能到达点i。

原因很简单：从start_station到它的下一站，是有可能有大于0的余油的；但是如果从start_station+1开始往i走，那么起始油量一定是0。有余油都跑不到i，更别提从0开始了。所以中间的所有点会被直接忽略掉。

4. 再次将起始点start_station记录为i+1，并将curr_tank置空，以重新模拟。
5. 最终判定，如果total_tank不为负数，说明存在点能够完成，并且最后一定是start_station符合条件。如果为负数，返回-1。

C++
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int total_tank = 0;
        int curr_tank = 0;
        int start_station = 0;
        
        for (int i = 0; i < gas.size(); i++) {
            total_tank += gas[i] - cost[i];
            curr_tank += gas[i] - cost[i];
            if (curr_tank < 0) {
                // Set Next Station as Start
                // Reset tank info
                start_station = i + 1;
                curr_tank = 0;
            }
        }
        
        return total_tank >= 0 ? start_station : -1;
    }
};