[2,3,1],[3,1,2]
1
从start出发, 如果油量足够, 可以一直向后走 end++; 油量不够的时候, start向后退 最终 start == end的时候,如果有解一定是当前 start所在位置
class Solution { public: int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { int start = gas.size() - 1; int end = 0; int sum = gas[start] - cost[start]; while(start > end){ if(sum >= 0){ sum += gas[end] - cost[end]; ++end; }else{ --start; sum += gas[start] - cost[start]; } } return sum >=0 ? start : -1; } };
这道题你会答吗?花几分钟告诉大家答案吧!
扫描二维码,关注牛客网
下载牛客APP,随时随地刷题