Gas Station

来源：Leetcode

原帖：http://oj.leetcode.com/problems/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. The solution is guaranteed to be unique.

代码：

 class Solution {  
 public:  
   //http://fisherlei.blogspot.com/search?q=gas  
   //0到n之间，找到第一个连续子序(这个子序列的结尾必然是n)大于0 从i起gas[i] >0,   
   //然后gas[i:i+1],until j, if Gas[i:j] < 0，then [i,j]都不能作为起点。  
   int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {  
     int N = gas.size();  
     int leftGas = 0, sum = 0, start = 0;  
     for (int i = 0; i < N; i++) {  
       int diff = gas[i] - cost[i];  
       leftGas += diff;  
       sum += diff;  
       if (sum < 0) {  
         start = i + 1;  
         sum = 0;  
       }   
     }  
     return leftGas >= 0 ? start : -1;  
   }  
 };