问题

有一条环形道路,沿着这条道路分布着 n 个加油站。每个加油站 i 提供的汽油量为 gas_i ,从加油站 i 到加油站 i+1 需要消耗的汽油量为 cost_i 。现在你要从某一个加油站出发,沿顺时针方向开车,绕着整个环形道路行驶一圈并返回到起点。你起步时油箱是空的。

你需要找到一个起点加油站,使得从该加油站出发,经过每个加油站时,汽油量始终不小于0,并能顺利返回出发点。

如果存在这样的起点,加油站编号是唯一的。如果不存在这样的起点,则说明无论从哪个加油站出发,都无法完成一圈。

示例

输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]

输出: 3

解释:

从 3 号加油站(索引为 3 处)出发,可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油

开往 4 号加油站,此时油箱有 4 - 1 + 5 = 8 升汽油

开往 0 号加油站,此时油箱有 8 - 2 + 1 = 7 升汽油

开往 1 号加油站,此时油箱有 7 - 3 + 2 = 6 升汽油

开往 2 号加油站,此时油箱有 6 - 4 + 3 = 5 升汽油

开往 3 号加油站,你需要消耗 5 升汽油,正好足够你返回到 3 号加油站。

因此,3 可为出发点。

解答

贪心算法

如果i开不到j,那么从i里面的任何一个作为起点都开不到j

所以下一次直接从j+1开始判断就行了