LeetCode/solutions/134. Gas Station.md

# [134. Gas Station](https://leetcode.com/problems/gas-station/)
# 思路
首先要明确能走完整个环的前提是gas的总量要不小于cost的总量，即gas与cost的差的和大于等于0。这个前提很好判断，遍历一遍就完事，关键在于如何确定起点。
需要注意的是题目说了如果起点存在，那么一定是唯一的。

## 思路一
假设开始设置起点start=0, 用overage表示当前剩余gas, 从`i = start`出发向后遍历，
计算剩余gas`total_overage += (gas[i]-cost[i])`, 如果当前total_overage不小于0则可以继续前进，
此时到下一个站点，按照同样方法计算total_overage。当到达某一站点时，这个值小于0了，则说明从起点到这个点中间的任何一个点都不能作为起点。
即我们可以更新start为i+1, 然后重置total_overage为0, 继续向后遍历，直到遍历完成。
另外我们可以在遍历的过程中顺便累加gas与cost的差，这样整个过程只需要一次遍历即可。

时间复杂度O(n)，空间复杂度O(1)。

## 思路二
我们也可以从后往前遍历，用一个变量max_overage来记录当前剩余油量的最大值。如果gas与cost的差的和大于等于0，那么max_overage所在位置即起点。

时间复杂度O(n)，空间复杂度O(1)。

# C++
## 思路一
``` C++
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int total_overage = 0, overage = 0, start = 0;
        for(int i = 0; i < gas.size(); i++){
            total_overage += (gas[i] - cost[i]);
            overage += (gas[i] - cost[i]);
            if(overage < 0){
                overage = 0;
                start = i+1;
            }
        }
        return (total_overage < 0)?-1:start;
    }
};
```

## 思路二
``` C++
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int total_overage = 0, max_overage = -1, start = 0;
        for (int i = gas.size() - 1; i >= 0; --i) {
            total_overage += gas[i] - cost[i];
            if (total_overage > max_overage) {
                start = i;
                max_overage = total_overage;
            }
        }
        return (total_overage < 0) ? -1 : start;
    }
};
```