Gas Station(Medium)加油站

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.

解题思路：贪心算法（Greedy Algorithm)

分析题目可以得到两个隐含的结论：

1. 若储油量总和sum(gas) >= 耗油量总和sum(cost)，则问题一定有解。
2. 若从加油站A出发，恰好无法到达加油站C（只能到达C的前一站）。则A与C之间的任何一个加油站B均无法到达C。

反证法: 假设从加油站A出发恰好无法到达加油站C，但是A与C之间存在加油站B，从B出发可以到达C。

而又因为从A出发可以到达B，所以A到B的油量收益（储油量 - 耗油量）为正值，进而可以到达C。

推出矛盾，假设不成立。

int canCompleteCircuit(int[] gas, int[] cost) {
    int sum = 0;
    int total = 0;
    int startingPoint = 0;

    for(int i = 0; i < gas.length; i++) {
        sum += gas[i] - cost[i];
        //小于0就只可能在i + 1或者之后了
        if(sum < 0) {
            startingPoint = i + 1;
            sum = 0;
        }
        total += gas[i] - cost[i];
    }

    if(total < 0) {
        return -1;
    } else {
        return startingPoint;
    }
}