LeetCode Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

Note:
The solution is guaranteed to be unique.

//思路：动规or贪心？
//1、设 vRemain[i]=gas[i]-cost[i]，如果vRemain[i]>=0则第i站的汽可以满足走向下一站，vRemain[i]<0则此战的汽不能满足走向下一站
//2、遍历vRemain[i]，每个vRemain[i]>=0都有可能是一个起点。累加后面的数据，若出现累加和<0的情况则不能到达下一站，需要重新选择新的起点
int canCompleteCircuit(vector<int> &gas, vector<int> &cost) 
{
	vector<int> vRemain;
	int n = gas.size();
	for(int i=0; i<n; i++)
		vRemain.push_back(gas[i] - cost[i]);

	for(int i=0; i<n; i++)
	{
		if(vRemain[i] >= 0)
		{
			//可能是一个可以开始的点
			int sum = 0;
			for(int j=i; j<n; j++)
			{
				sum += vRemain[j];
				if(sum < 0)
					break;				
			}

			if(sum >= 0)
			{
				for(int k=0; k<i; k++)
				{
					sum += vRemain[k];
					if(sum < 0)
						break;
				}
			}

			if(sum >= 0)
				return i;
		}
	}

	return -1;
}