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個加油站。簡單粗暴的方法一定是：每個加油站為起點(diǎn)，然后遍歷一圈，那么復(fù)雜度就是o(n^2)。顯然，這道題不是讓我們給出這樣的答案！ 2. 復(fù)雜度至少應(yīng)該是o(nlgn)，最好的是o(n)。 3. 想了半天，剛開始是想從左往右遍歷，在每個位置處gas[i]-cost[i]得到剩余的油，如果為負(fù)值，說明需要從左邊挪一些油；為正值，則說明這個汽油站可以為后面的汽油站貢獻(xiàn)一些油。換一種說法：油的轉(zhuǎn)移有方向性，只允許從左邊往右邊轉(zhuǎn)移。這樣的題，油的轉(zhuǎn)移從左往右，那么我們從右往左遍歷的話，遇到負(fù)值，我們知道肯定由前面轉(zhuǎn)移過來，所以把這個負(fù)值累加到前面去，如果在某個位置的累加值大于0，則說明從這個位置其可以保證后面的都順利到達(dá)，但是這個站前面的還不一定，所以，需要繼續(xù)往前累加，找到最大的累加值的站肯定就是可以作為起始點(diǎn)了！