LeetCode 134. 加油站

原题目：https://leetcode-cn.com/problems/gas-station/

 

思路：

如果可以绕行一圈，那么需要满足两个条件

1、车子可以从i开到i+1，即车子开到i+1使得油tmp≥0

2、全程油的量要大于耗费的量 sum ≥ cost

实现：

用ai表示gas[i] - cost[i]，tmp += ai, sum += ai

如果开到i时，tmp<0，那么就意味着开不到i，所以要从i+1出发。此时对tmp清零。

如果sum<0，就返回-1。否则返回上一步求得的值。

 

代码：

class Solution { public: int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { int index=0,n=gas.size(); int sum = 0,tmp = 0; for(int i=0;i<n;i++){ sum += gas[i] - cost[i]; tmp += gas[i] - cost[i]; if(tmp<0){ index = i+1; tmp = 0; } } return sum <0 ? -1 : index; } };