134. Gas Station

There are two important points:

1. if the total gas is larger or equal than cost, there must be a solution.

2. if the car starts from A but can't reach B, there mustn't be solution between A and B. This can be proved contradictorily. If there is K between A and B that the car can reach from A to K and reach from K to B, then the car must be able to reach B from A, which is contracting the assumption.

So, we can solve the problem by greedy, i.e., once we can't reach i' from i, then the start station must be i+1. If the total gas is larger or equal than the cost, the start station will be a valid solution.

1:  class Solution {  
2:  public:  
3:    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {  
4:      vector<int> diff(gas.size(), 0);  
5:      int totalGas = 0, start = 0, leftGas= 0;  
6:      for (int i = 0; i < gas.size(); i++) {  
7:        diff[i] = gas[i] - cost[i];  
8:      }  
9:      for (int i = 0; i < gas.size(); i++) {  
10:        totalGas += diff[i];  
11:        leftGas += diff[i];  
12:        if (leftGas < 0) {  
13:          start = i+1;  
14:          leftGas = 0;  
15:        }  
16:      }  
17:      return totalGas >= 0 ? start : -1;  
18:    }  
19:  };