P196. 加油站

leetcode 134 lintcode 187 贪心 讨论

温馨提示:您没有权限查看当前视频。 立即购买观看视频

描述

这个题目说的是,在一条环形公路上有 n 个加油站,编号是 0 ~ n-1。第 i 个加油站提供的油量是 gas[i],从第 i 个加油站开到第 i+1 个加油站需要的油量是 cost[i]。

给你一辆油箱容量无限大的汽车,并且一开始油箱为空。你要计算出,是否可以从某个加油站开始,顺时针绕环形公路一周。如果可以,返回出发加油站的编号;否则,返回 -1。

注意,给你的 gas 数组和 cost 数组都不为空,并且长度相同。另外,这个题目保证,要么不存在绕行公路一周的方案,要么就只有唯一一个出发点,可以绕行公路一周。

比如说,给你的 gas 数组和 cost 数组是:

gas:  [1, 2, 4, 8]
cost: [4, 8, 1, 2]

只要从编号为 2 的加油站开始,就可以顺利绕行公路一周:

// 到达 3 号加油站时的油量
0 + 4 - 1 = 3

// 到达 0 号加油站时的油量
3 + 8 - 2 = 9

// 到达 1 号加油站时的油量
9 + 1 - 4 = 6

// 回到 2 号加油站时的油量
6 + 2 - 8 = 0

这样就从 2 号加油站出发,顺利绕行一周,回到 2 号加油站。因此你要返回的出发加油站编号就是 2。

关于 AlgoCasts

AlgoCasts 旨在用心做好每一个算法讲解视频。每个视频包含两个部分:题目的剖析讲解以及编码,力求在讲解清楚到位的基础上,尽可能地保持视频精简短小,让大家可以在碎片时间里进行学习,并收获这些算法题背后的思想与乐趣。