首页 > 代码库 > leetcode - Gas Station

leetcode - Gas Station

//假设sum为总的耗油量,max为起始点a到终点b的耗油量,如果,当到达b的时候,
//max < 0,那么,出发点肯定不能从a开始,这个时候将max = 0,然后,pos = i+1,选择pos为起始点,然后继续遍历。
//如果,最后的sum < 0,那么,返回-1,如果,sum >= 0,则返回pos.
class Solution {
public:
    int canCompleteCircuit(std::vector<int> &gas, std::vector<int> &cost) {
		int max = 0,sum = 0,pos = 0,sz = gas.size();
		for (int i = 0; i < sz; i++)
		{
			sum += gas[i] - cost[i];
			max += gas[i] - cost[i];
			if(max < 0)
			{
				max = 0;
				pos = i+1;
			}
		}
		return sum >= 0 ? pos : -1;
    }
};

leetcode - Gas Station