题解 | #加油站#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param gas int整型vector 
     * @param cost int整型vector 
     * @return int整型
     */
    // 贪心法
    int gasStation(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        int res = 0, sum = 0, start = 0;
        
        for(int i=0; i<n; i++){
            res += gas[i] - cost[i];
            sum += gas[i] - cost[i];
            if(res < 0){
                start = (i+1)%n;
                res = 0;
            }
        }
        
        return sum >= 0 ? start : -1;
    }
    /*
    // 遍历所有起始点
    int gasStation(vector<int>& gas, vector<int>& cost) {
        // write code here
        int n = gas.size();
        int res;
        for(int i=0; i<n; i++){
            int cur = 0;
            res = gas[i];
            int start = i;
            while(res > 0){
                res = res - cost[(start % n)];
                if(res < 0){
                    break;
                }
                cur += 1;
                res += gas[(start + 1)%n];
                if(cur == n){
                    return i;
                }
                start += 1;
            }
        }
        
        return -1;
    }
    */
};