First I thought of a DP solution.. but TLE. So there must be a O(n). I thought of Mono-Queue.. but looks too complex.
So what is the naive solution? O(n^2) of course. If we pick next start station smartly, we can make it linear: http://blog.csdn.net/kenden23/article/details/14106137
Smart idea... I need practice more and think more....
class Solution { public: int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { size_t cnt = gas.size(); if (cnt == 1) { if (gas[0] >= cost[0]) return 0; return -1; } for (int i = 0; i < cnt; i++) { int delta = 0; int step; bool bFound = true; for (step = 0; step < cnt - 1; step++) { delta += gas[(i + step) % cnt] - cost[(i + step) % cnt]; if (delta < 0) { i += step; bFound = false; break; } } if (!bFound) continue; if (delta > 0) return i; else i += step - 1; } return -1; } };
LeetCode "Gas Station" - TO BE REVISED,布布扣,bubuko.com
LeetCode "Gas Station" - TO BE REVISED
原文：http://www.cnblogs.com/tonix/p/3926979.html