77 lines
2.4 KiB
Markdown
77 lines
2.4 KiB
Markdown
# 毎日一题 - 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，就说明不行，我们继续遍历下一个
|
||
```js
|
||
// 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总和
|
||
>
|
||
```js
|
||
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;
|
||
```
|
||
|
||
## 优秀解答
|
||
|
||
>暂缺
|