力扣 每日一题134.加油站

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int sumgas=0;         //加油站总油量
        int sumcost=0;        //行驶所需总油量
        int val[gas.size()];  //第i个加油站灌输油量与到达下一个加油站所用油量差值，如果为正数则说明到下站有油量剩余，反之说明需要消耗上一站的剩下的油量
        for(int i=0;i<gas.size();i++){
            sumcost+=cost[i];
            sumgas+=gas[i];
            val[i]=gas[i]-cost[i];
        }
        if(sumgas<sumcost){  //当加油站的总油量小于行驶所需总油量时，必定不可能环绕一周，反之则必然可以。
            return -1;
        }
        int valsum=val[0];
        int res=0;
        for(int i=1;i<gas.size();i++){
            if(valsum<0){   //valsum<0，则说明从该第res个站开始行驶不行，重新设置新的起始站
                res=i;
                valsum=val[i];
            }
            else{
                valsum+=val[i];
            }
        }
        return res;
    }
};

由于答案唯一，所以起始站必定是val为负数后的第一个正数（如果val为负数后的第二个正数可以实现该题，则val为负数后的第一个正数必定也可以实现，不符合该题要求），当valsum<0时，说明该值为val[i-1]为小于0的值，且以res为起始点的加油站不能行驶完一圈（也说明了以res到i-1中任意一个站为起点的加油站不能行驶完一圈，以其中任意一个站为起点必定小于等于valsum），故设置新的i值为res。