134. 加油站 Python

加油站、Python

这道题目涉及到了贪心算法。

首先，我们需要明确一个结论：如果汽车从 $A$ 站出发，到不了 $B$ 站，那么从 $A$ 和 $B$ 中间任何一个站出发都到不了 $B$。

有了这个结论，我们假设当前在第 $i$ 个加油站，且车上还有 $now$ 升汽油。我们可以一直向前走，同时不断更新 $now$ 的值，当 $now<0$ 时说明无法到达下一个加油站，此时就需要选择当前能够到达的所有加油站中（包括自己），选择一个油量最大的加油站前往，同时将加油次数 $ans$ 加 $1$。

时间复杂度为 $O(n)$。

参考代码：

```python
def canFinish(distance: List[int], fuel: List[int], start: int) -> int:
now, ans = fuel[start], 0
for i in range(start, len(distance)):
now -= distance[i]
if now < 0:
max_fuel = max(fuel[start:i+1])
if max_fuel <= 0:
return -1
now += max_fuel
ans += 1
start = i
return ans
```

[[1](