---恢复内容开始---
这道题考察的可能偏向逻辑的思考能力。
最有效的方法是时间复杂度为O(n)，空间复杂度为O(1).这种高效算法，参考一个前辈的思想：“My linear solution based on a observation that, if you stops at certain gas station, the gas stations previous to the station you stop must not be a valid starting point. ”
意思是说从某个station开始，如果不能回到这个station，而是停在中间某一个station，那么从start到stop的这些station都不能作为汽车的起点。
下面是AC代码：
/** * * @param gas * @param cost * @return Return the starting gas station‘s index if you can travel around * the circuit once, otherwise return -1. */ public int canCompleteCircuit(int[] gas, int[] cost) { int left = 0; int start=0, i; int N = gas.length; while(true) { i = start; left = 0; while(left+gas[i%N]-cost[i%N]>=0) { left = left+gas[i%N]-cost[i%N]; i++; if(i%N == start%N) return i%N; } if(i>N-1) return -1; start = ++i; } }
---恢复内容结束---
LeetCode OJ - Gas Station,布布扣,bubuko.com
原文：http://www.cnblogs.com/echoht/p/3690192.html