134. 加油站
image.png

思路

还是没想出来，看题解了。
有暴力法和贪心法【我怎么连暴力都没写出来哎】
for循环适合模拟从头到尾的遍历，而while循环适合模拟环形遍历，要善于使用while！

暴力：

  • 时间复杂度：$O(n^2)$

  • 空间复杂度：$O(n)$ ```javascript var canCompleteCircuit = function(gas, cost) { let start =0; let restGas =0; //暴力遍历每一个起点，去判断能否跑完一圈 for(let i=0;i<gas.length;i++){

    1.   restGas =gas[i]-cost[i];
    2.   let index =(i+1)%gas.length;
    4.   while(restGas>0 &&index!==i){
    5.       restGas +=gas[index]-cost[index];
    6.       index =(index+1)%gas.length;
    7.   }
    8.   if(restGas>=0 &&index ===i){
    9.   return  index;
    10.   }

    } return -1;

};

<a name="Kh0Xo"></a>
## 贪心算法（方法一）
直接从**全局进行贪心选择**，情况如下：

- 情况一：如果gas的总和小于cost总和，那么无论从哪里出发，一定是跑不了一圈的
- 情况二：rest[i] = gas[i]-cost[i]为一天剩下的油，i从0开始计算累加到最后一站，如果累加没有出现负数，说明从0出发，油就没有断过，那么0就是起点。
- 情况三：如果累加的最小值是负数，汽车就要从非0节点出发，从后向前，看哪个节点能这个负数填平，能把这个负数填平的节点就是出发节点。

时间复杂度：$O(n)$<br />空间复杂度：$O(1)$
<a name="n7qUy"></a>
## *贪心算法（方法二）【有一些KMP思想在里面】
可以换一个思路，首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。<br />每个加油站的剩余量rest[i]为gas[i] - cost[i]。<br />i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，起始位置从i+1算起，再从0计算curSum。<br />**那么局部最优：当前累加rest[j]的和curSum一旦小于0，起始位置至少要是j+1，因为从j开始一定不行。全局最优：找到可以跑一圈的起始位置**。<br />![image.png](https://cdn.nlark.com/yuque/0/2022/png/2450083/1648091183478-730d0c66-06ac-4a0b-9d58-0cbbba16d5d6.png#clientId=ua0110b59-f5d9-4&from=paste&id=u9de1c945&margin=%5Bobject%20Object%5D&name=image.png&originHeight=1756&originWidth=2548&originalType=url&ratio=1&size=432629&status=done&style=none&taskId=u84e57281-64ec-4a6d-b673-5359a5d9cf9)

- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$
```javascript
var canCompleteCircuit = function(gas, cost) {
    const gasLen = gas.length
    let start = 0
    let curSum = 0
    let totalSum = 0

    for(let i = 0; i < gasLen; i++) {
        curSum += gas[i] - cost[i]
        totalSum += gas[i] - cost[i]
        if(curSum < 0) {
            curSum = 0
            start = i + 1
        }
    }

    if(totalSum < 0) return -1

    return start
};