本次刷题日记的第 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. 加油站
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
