前言

今天也是一道中等难度的题

题目

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

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

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

示例 1:

示例 2:

提示:

• gas.length == n
• cost.length == n
• 1 <= n <= 105
• 0 <= gas[i], cost[i] <= 104

分析

韩信带净化：一维数组一般情况下可以做到O(n)的时间复杂度

这道题咋一看很简单，我们只需要找一个起始点油量大于0的不就好了？

但是这是错的，没有考虑一点：如果中间没油呢？这就断了，走不通了。

所以我们要找的不仅仅是起始油量大于0的，还需要找之后的路一直不会小于0的

并且这里还有个特点，如果第i个起始位置走到j的位置发现断了，那么i到j之间的点都不能作为起始点。

那么这就很简单了，我们只需要判断从i的位置开始到len是否都大于0即可，并且中间可以跳过，那就意味着没必要都从i + 1开始，所以时间复杂度为O(n)。

另外要判断是否有解，还需要记录0 - len这个过程中的总油量，大于0则必定有解。

解

代码很简单，不多说

测试用例

总结

这道题没啥好说的，总结两点：

1. 总油量大于0则必定有解
2. 如果第i起始点在j位置断了，那么i - j之间的起始点都可以跳过。