2019-06-04.md

毎日一题 - 134.Gas Station（加油站）

信息卡片

• 时间：2019-06-04
• 题目链接：https://leetcode-cn.com/problems/gas-station/
• tag：Array

题目描述

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

参考答案

1.暴力求解，时间复杂度O(n^2)

我们可以一次遍历gas，对于每一个gas我们依次遍历后面的gas，计算remian，如果remain一旦小于0，就说明不行，我们继续遍历下一个

// bad 时间复杂度0（n^2）
let remain = 0;
const n = gas.length;
for (let i = 0; i < gas.length;i++){
    remain += gas[i];
    remain -= cost[i];
    let count = 0;
    while (remain >= 0){
        count++;
        if (coun === n ) return i;
        remain += gas[getIndex(i + count,n)];
        remain -= cost[getIndex(i + count,n)];
    }
    remain = 0
}
retirn -1;

2.比较巧妙的方法，时间复杂度是O(n)

这个方法基于两点：

2-1:如果站点i到达站点j走不通,那么从i到j之间的站点（比如k）出发一定都走不通。前提i（以及i到k之间）不会拖累总体（即remain >= 0）。

2-2:如果cost总和大于gas总和，无论如何也无法走到终点，这个比较好理解。因此假如存在一个站点出发能够到达终点，其实就说明cost总和一定小于等于gas总和

const n = gas.length;
let total = 0;
let remain = 0;
let start = 0;

for(let i = 0; i < n; i++){
    total += gas[i];
    total -= cost[i]

    remain += gas[i];
    remain -= cost[i];

    // 如果remain < 0,说明从start到i走不通
    // 并且从start到i走不通，那么所有的solution中包含start到i的肯定都走不通
    // 因此我们重新从i + 1开始作为start
    if (remain < 0){
        remain = 0;
        start = i + 1;
    }
}
// 事实上，我们遍历一遍，也就确定了每一个元素作为start是否可以走完一圈

// 如果costu总和大于gas总和，无论如何也无法走到终点
return total >= 0? start : -1;

优秀解答

暂缺