题目描述

在一条循环路线上有N个加油站,索引为i的加油站具有的油量为gas[i]。

你有一辆具有不限容量油箱的小汽车,并且这辆车从第i个加油站到第i 1个加油站耗费的油量是cost[i],初始的时候你的小汽车的油箱里面没有油,你需要寻找一个站点作为起点。

如果从某个起点出发可以保证你开着你的车绕着赛道走一圈,则返回起点的加油站下标,否则返回-1

返回起点加油站的下标。

比如下图:

8分钟搞懂新算法(今日算法加油站问题)(1)

加油站上的数字代表该加油站具有的油量,圆圈上的数字代表该路段需要耗费的油量,那么小车该从哪个加油站出发才能保证顺利走一圈呢?

注意:给出的实例可以保证解决方案是唯一的。

解题思路

简单地想,我们当然是想从第1个加油站出发,到达下一个加油站时车里剩余的油尽可能多,这样车里剩下的油还可以继续后面的路程,所以,采取贪心的思路,首先计算从每一站出发,到达下一站后车里还能剩余的油,然后按照剩余油的多少进行排序,从可以剩余油最多的站出发,进行模拟行程,看最后可否走一圈,如果不可以,则换下一个起点。

代码

核心代码:

8分钟搞懂新算法(今日算法加油站问题)(2)

8分钟搞懂新算法(今日算法加油站问题)(3)

可以求得上例中的答案为0,即从第0号加油站出发,就像下面这样:

全部代码见github:https://github.com/DmrfCoder/AlgorithmAndDataStructure/blob/master/LeetCode/src/seventeen/Solution.java

,