题目描述#

在一条环形道路上共有 n 个加油站，第 i 个加油站拥有 gas[i] 升汽油。

从第 i 个加油站开往第 i+1 个加油站需要消耗 cost[i] 升汽油（n-1 的下一个为 0）。

你从某个加油站出发，初始油箱为空，油箱容量无限。如果能够绕环路一周返回出发点，则返回该加油站的下标，否则返回 -1。

若存在解，题目保证它是唯一的。

知识边界#

贪心算法#

本题使用贪心思想。

若从某个起点 start 出发，在位置 i 出现油量不足：

sum(start → i) < 0

那么 start 到 i 之间的任何位置都不可能成为起点，因此可以直接把起点更新为 i+1。

Go 中的遍历方式#

Go 中通常使用普通 for 循环遍历数组：

for i := 0; i < len(gas); i++ {
}

本题维护三个变量：

• total：全局油量差
• cur：当前路径油量
• ans：候选起点

常见错误#

1. 忘记判断 total < 0
2. 起点更新应该是 i+1
3. cur < 0 时必须重置为 0

思路#

思路一#

定义：

diff = gas[i] - cost[i]

遍历每个加油站：

1. total += diff

2. cur += diff

3. 如果 cur < 0，说明当前起点无法到达 i+1

   • 更新起点 ans = i + 1
   • cur 重置为 0

遍历结束后：

如果 total < 0，说明总油量不足，返回 -1。 否则 ans 就是唯一合法起点。

时间复杂度：O(n)

空间复杂度：O(1)

该方法通过贪心跳过所有不可能的起点，因此最终得到唯一解。

代码#

func canCompleteCircuit(gas []int, cost []int) int {
	total := 0
	cur := 0
	ans := 0
	for i := 0; i < len(gas); i++ {
		diff := gas[i] - cost[i]
		total += diff
		cur += diff
		if cur < 0 {
			cur = 0
			ans = i + 1
		}
	}
	if total < 0 {
		return -1
	}
	return ans
}