【访谈经典150 |阵]加油站

写在前面

本专栏重点分析和讲解【访谈经典150】算法。每两到三天更新一篇文章。欢迎更新...

专栏内容主要是对专题进行分析，对本专题涉及到的数据结构等内容进行一些回顾和总结。文章结构大致如下，部分内容会增删：

• 标签：介绍本题涉及的知识点和数据结构；
• 题目来源：粘贴题目链接，方便大家找到题目并完成练习；
• 问题解读：重述问题（确保自己真正理解问题的含义），并强调问题的一些关键信息；
• 解题思路：介绍一些解题思路，每个解题思路包括思路解释、实现代码和复杂度分析；
• 知识回忆：重点回顾今天介绍的内容，回顾总结题目的关键内容和数据结构。

标签

【一次遍历】【数组】

问题来源

访谈经典150 | 134.加油站

问题解释

环形路上的加油站数量有限。每个加油站均可获得相应的油品。从一个加油站到下一个加油站需要消耗一些汽油。您可以从环路上的任何加油站出发，前往下一个加油站。如果可以从某个加油站出发并返回出发的加油站，请返回加油站编号（从0开始），否则返回-1。

如果存在解决方案，则保证它是唯一的。

解决问题的方法

方法一：暴力枚举

我们遍历各个加油站，从每个加油站出发，确定可以绕到哪个起点。如果从某个起点出发，能够顺利跑完一圈，而不会在下一个加油站耗尽燃料，那么这个起点就是唯一的答案。

很容易想到的方法，要么实现起来困难，要么时间复杂度太高。极少数情况下，最容易想到的方法就是最佳解决方案。蛮力解决方案的时间复杂性为$o（n^2）$，$n$ 是加油站的数量。本题数据量达到 $10^5$, $O({n\; 的时间复杂度}^2)$必须超时。

方法二：一次通过

注剩余=gas[i] - cost[i]表示从i到达下一个加油站后剩余的燃油量（包括加油和消耗）。

特殊情况：如果完成一圈后剩余燃油量小于0，则表示无论从哪个起点开始都无法完成一圈。此时返回-1。

接下来，我们将遍历到达的加油站，并使用变量start来记录起始位置。变量currSum表示从0到当前i的累积剩余油量。如果currSum < 0，则表示区间[0, i]不能作为起点（因为如果在这个区间选择任意一个起点，都可以去加油站i 将全部耗尽燃料）。此时起始位置只能从i+1开始计算。我们还需要更新 currSum = 0 以开始新的累积。

最后直接返回start，这是唯一的起点。

特殊情况，我们不需要在完成一圈后独立计算剩余油量totalSum，我们可以在一次遍历中计算出来。

实现代码

类 解决方案 {
公共：intcanCompleteCircuit（矢量） <int>&气体 ,向量<int>&成本) {int currSum = 0; int 总和 = 0;  //记录一圈后剩余燃油量int  开始 = 0; (int) 我=0;我<气体.尺寸(); ++i){ int休息=气体[i] -成本[i ];当前总和+=休息;总和+= 休息;如果 (currSum < 0) {开始  =  i + 1; currSum  = 0;}}//完成一圈后剩余燃油量 < 0if  (总和 <  0) 返回 - ;返回开始;}};

复杂性分析

时间复杂度：$O(n)$，$n$ 是数字加油站。

空间复杂度：$O(1)$。

写在最后

如果文章内容有错误或者对文章有任何疑问，欢迎私信博主或者在评论区指出💬💬💬。

如果你有更好的时间和空间复杂度方法，欢迎在评论区分享。

最后，感谢您的阅读。如果你觉得自己学到了一些东西，可以给博主一个👍。