【刷题日记】134. 加油站

本次刷题日记的第 96 篇，力扣题为：134. 加油站

一、题目描述：

咱今天来做一个模拟生活中的一个题目，加油站的题目

二、这道题考察了什么思想？你的思路是什么？

看完题目，其实题目给我们呈现的是一个环形的路，路上有多个加油站，题目要求我们按照给出的条件，找出能够从某一个加油站开始出发，可以按照环路跑下去，能够回到起点加油站的那一个加油站，此处的加油站对应这题目中给出的数组索引

• 题目给出咱们 2 个数组，gas[i] 表示 第 i 个加油站，可以添加 gas[i] 升汽油 ， 给出的 cost[i] 表示从第 i 个加油站，到下一个加油站需要消耗的汽油
• 要求咱们找到哪一个加油站可以一出发，就可以顺着环行一周，回到起点加油站

分析

其实看到这个题目，也是非常依赖题目给出的数据，就这么看肯定是看不出来到底哪一个加油站正好可以出发，且能环行一周又回到这个加油站

那么，我们就要每一个加油站都去看一下，如果从第 0 个加油站看是走，那么就先加油 gas[0] ，这个时候，继续往下一个加油站走的时候，需要减去 cost[0] ，并且这个时候，能够顺利到第 1 个加油站的话，那么就再加上 gas[1] ，依次类推

举个例子

例如，按照上述逻辑，假如有 5 个加油站，我们发现从第 1 个加油站开始跑，跑到第 3 个加油站的时候，发现没有办法跑到第 4 个加油站，那么这个时候，说明咱们从 第 1 个加油站出发肯定是行不通的，因此咱们就需要从 第 4 个加油站为出发点开始环形（因为此时如果从2 和 3 为起始点，没有意义） ，直到咱们能找到题目要求的加油站为止，如果发现以 第 5 个加油站为起始点，也是没发满足题目要求的，那么就直接返回 -1

那么，按照这个思路，我们只需要去实现代码，手撸代码就可以了，模拟从第 1 个加油站开始，查看是否 ok，如果不 ok ，就从模拟完上一轮的加油站的下一个开始

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码

• 此处需要注意上述例子说到的，需要注意例子中的情况

编码如下：

func canCompleteCircuit(gas []int, cost []int) int {
    for i, n := 0, len(gas); i < n; {
        sumOfGas, sumOfCost, cnt := 0, 0, 0
        for cnt < n {
            j := (i + cnt) % n
            sumOfGas += gas[j]
            sumOfCost += cost[j]
            if sumOfCost > sumOfGas {
                break
            }
            cnt++
        }
        if cnt == n {
            return i
        } else {
            i += cnt + 1
        }
    }
    return -1
}

四、总结：

本题咱们的实现方式，实际上是遍历了一次题目给出的 gas 和 cost ，因此时间复杂度是 O(n)，空间复杂度的话，是 O(1)，我们只引入了常数级别的空间消耗

原题地址：134. 加油站

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~