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，則說明從這個位置其可以保證后面的都順利到達，但是這個站前面的還不一定，所以，需要繼續往前累加，找到最大的累加值的站肯定就是可以作為起始點了！
class Solution {public: int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { // int mxsum=0,sum=0,pos=0; for(int i=cost.size()-1;i>=0;i--){ sum+=gas[i]-cost[i]; if(sum>mxsum){ pos=i; mxsum=sum; } } return sum>=0?pos:-1; }};新聞熱點
疑難解答
