在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则保证它是唯一的。

我觉得我的思路很笨就是找到第一个可以往下走的如果可以顺利的话那么就OK 如果不顺利那么就继续往下找因为解是唯一的所以只要找到直接return就行虽然不确定是不是会超过时间限制但是还是先试一下

我的大体思路就是：我往下找找到第一个满足的就开始计算步数和余量只要往下走就往下走步数要走到n才行计算此时的索引就使用取模的方法如果到了什么时候rem<0 那么就break 不然就step+=1 如果等于n了那么就return i （反正要么就是while结束了要么就是break了）如果并没有return i 那么就证明是这个不行那要继续往下选择

那么重点来了我要使用i+1吗？显然不是因为我走了step步之后无法走下去那么选择i和i+step中间的是可以保证走下去的吗？

跳过失败路径中的所有站点是贪心算法的关键优化点之一，它能将时间复杂度从 O(n²) 降到 O(n)。这不是因为“某一步负数太多”，而是因为整个路径的净收益是负的，意味着从任何子起点都无法完成一圈。所以继续进行的就是i+step+1

但是我领会到其中的奥妙了你想啊我从中间的出发根本到不了下一步为什么？我既然是走到这步才停证明是因为前面的是有剩余的到我这步又亏损了亏损大了才到不了那你可能会觉得诶那我从亏损超级大的那一步往下走到不了吗？你想啊你既然是从亏损超级大的那一步往下走既然可以往下走就证明有剩余有剩余都走不到这个step步那中间的哪一个都不行（因为要想到达中间的某一步任何一步都是要有结余的有结余还不行那么我从头开始更不行）我少了前面的补贴还要面对后面的亏损达咩达咩

好的来看代码

class Solution(object):def canCompleteCircuit(self, gas, cost):i=0index=-1n=len(gas)while i <n:#如果当前的汽油不够消耗到下一步的 就继续往下找if gas[i]<cost[i]:i+=1continue#如果找到了这一个gas = [1,2,3,4,5], cost = [3,4,5,1,2]#现在是索引为3的地方 那么要是继续往下走 就要满足gas-cost+gas>=cost#计算剩余量和步数rem=0step=0while step<n:j = (i + step) % nrem += gas[j] - cost[j]if rem < 0:breakstep += 1if step==n:return i#证明这个i是不行的 那么我是需要走i+1的这一步的吗？#不是的 因为我从i开始可以的 证明我i这步是有盈余的 既然走到这步不行了#那么就证明无论我从中间的哪一步开始 走到这步肯定都不行了 所以要跨过step这个步骤开始else:i=step+i+1return -1
solution=Solution()
result=solution.canCompleteCircuit([2,3,4], [3,4,3])
print(result)

但是这个运行速度只超过百分之三十多所以我们来分析一下排名第一的代码

首先就是计算总和如果消耗总和大于油量总和那直接不行

然后就是直接计算盈余一旦盈余小于0 改变开始的索引？感觉这个for循环写的还是挺深奥的如果小于0的话证明这个起点不行那么是尝试下一个这个我明白但是为什么直接每个点开始计算结余呢？从第一个点开始如果这个剩余小于0 那这个点不行使用i+1这个点如果是大于0的那么这个点就不变 i继续往下走在这个过程中只要这个剩余小于0 就证明这个包括这个中间的点都是不行的（看我上面的解释）喵喵喵啊

class Solution(object):def canCompleteCircuit(self, gas, cost):""":type gas: List[int]:type cost: List[int]:rtype: int"""if sum(gas) < sum(cost):return -1cursum = 0start_idx = 0for i in range(len(gas)):cursum += gas[i] - cost[i]if cursum < 0:start_idx = i + 1cursum = 0return start_idx

如果喜欢这个帖子欢迎点赞收藏！