温馨提示:您没有权限查看当前视频。 立即购买观看视频
这个题目说的是,在一条环形公路上有 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 旨在用心做好每一个算法讲解视频。每个视频包含两个部分:题目的剖析讲解以及编码,力求在讲解清楚到位的基础上,尽可能地保持视频精简短小,让大家可以在碎片时间里进行学习,并收获这些算法题背后的思想与乐趣。