【Leetcode】134. Gas Station


我们首先要知道能走完整个环的前提是gas的总量要大于cost的总量,这样才会有起点的存在。假设开始设置起点start = 0, 并从这里出发,如果当前的gas值大于cost值,就可以继续前进,此时到下一个站点,剩余的gas加上当前的gas再减去cost,看是否大于0,若大于0,则继续前进。当到达某一站点时,若这个值小于0了,则说明从起点到这个点中间的任何一个点都不能作为起点,则把起点设为下一个点,继续遍历。当遍历完整个环时,当前保存的起点即为所求。

* 我们从0开始以其为起点实验,累加 restGas += gas[i] - cost[i],一旦在 i 处遇到restGas<0,

* 那么就说明当前选择的起点beg不行,需要重新选择,此时我们不应该回去使用 beg+1 作为新起点,

* 因为在beg处,一定有 gas>=cost,说明 beg+1 到 i 处的总gas一定小于总的cost,

* 选择其中任何一个作为起点还是不行的,所以应该跳过这些点,以 i+1 作为新起点,

* 遍历到 size-1 处就可以结束了,如果找到了可能的起点,我们还要进行验证,走一遍(total),

* 如果没问题那么说明可以。

* 其实本质就是:这个起点将路径分为前后两段,前段总的余量为负,

* 即油不够用,要想有解,那么后段油量应该为正,此时才可能有解,

* 我们要做的就是找到这个分割点作为起点,然后再验证一下;反之,

* 如果前段就为正了,那么显然可以直接选择前面的点为起点;如果整段

* 加起来都是负的,那么无解

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容