Leetcode 134. 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.

s思路： 1. n个加油站。简单粗暴的方法一定是：每个加油站为起点，然后遍历一圈，那么复杂度就是o(n^2)。显然，这道题不是让我们给出这样的答案！ 2. 复杂度至少应该是o(nlgn)，最好的是o(n)。 3. 想了半天，刚开始是想从左往右遍历，在每个位置处gas[i]-cost[i]得到剩余的油，如果为负值，说明需要从左边挪一些油；为正值，则说明这个汽油站可以为后面的汽油站贡献一些油。换一种说法：油的转移有方向性，只允许从左边往右边转移。这样的题，油的转移从左往右，那么我们从右往左遍历的话，遇到负值，我们知道肯定由前面转移过来，所以把这个负值累加到前面去，如果在某个位置的累加值大于0，则说明从这个位置其可以保证后面的都顺利到达，但是这个站前面的还不一定，所以，需要继续往前累加，找到最大的累加值的站肯定就是可以作为起始点了！