题解 | #加油站#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param gas int整型vector 
     * @param cost int整型vector 
     * @return int整型
     */
    int gasStation(vector<int>& gas, vector<int>& cost) {
        // write code here
        int n = gas.size();
        int total_tank = 0, curr_tank = 0;
        int starting_station = 0;

        for (int i = 0; i < n; ++i) {
            total_tank += gas[i] - cost[i];
            curr_tank += gas[i] - cost[i];

            // 如果当前累积油量小于 0，说明从 starting_station 到 i 无法完成，需要重新设定起点
            if (curr_tank < 0) {
                starting_station = i + 1; // 新的起点放在 i 后面
                curr_tank = 0; // 油箱油量重置
            }
        }
        
        // 如果总油量大于等于总耗油量，说明可以完成一圈
        return total_tank >= 0 ? starting_station : -1;
    }
};