加油站（134）

题目

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

说明

如果题目有解，该答案即为唯一答案。 输入数组均为非空数组，且长度相同。 输入数组中的元素均为非负数。

示例

输入: gas = [1,2,3,4,5] cost = [3,4,5,1,2]

输出: 3

输入: gas = [2,3,4] cost = [3,4,3]

输出: -1

算法

暴力法

export const canCompleteCircuit_1 = (gas, cost) => {
	let res = 0;
	for (let i = 0; i < gas.length; i++) {
		let carGas = 0;
		for (let j = 0; j < gas.length; j++) {
			carGas += gas[j];
			carGas -= cost[j];
			if (carGas < 0) {
				break;
			}
			if (j === gas.length - 1) {
				return res;
			}
		}
		gas.push(gas.shift());
		cost.push(cost.shift());
		res++;
	}
	return -1;
};

数学推理

能完成一圈，需要满足两个条件：

• 总汽油数 > 总消耗数
• 在第i个汽油站，应该满足gas[i]-cost[i]>0才能到达下一个加油站

下面只需要O(N)时间复杂度的算法就可以：

• 从第0个加油站开始，totalGas是从0开始经过的每一站的净汽油数（cost-gas），currentGas是当前出发汽油站的情况下的净汽油数
• 按顺序每经过一个加油站，让totalGas和currentGas分别加上gas[i]和减去cost[i]，如果currentGas不小于零，那么汽车可以驶往下一个加油站；如果currentGas小于零，那么说明汽车不能驶向下一个加油站且从startStation到这个加油站之前的所有加油站出发都不能让汽车驶向下一个加油站，那么让startStation指向下一个加油站且cueerntGas重置为0
• 直到汽车抵达最后一个加油站，判断totalGas是否小于0，如果小于0那么汽车不能循环一圈，如果不小于零，那么startStation为汽车起点

export const canCompleteCircuit = (gas, cost) => {
	let startStation = 0,
		totalGas = 0,
		currentGas = 0;
	for (let i = 0; i < gas.length; i++) {
		totalGas = totalGas + gas[i] - cost[i];
		currentGas = currentGas + gas[i] - cost[i];
		if (currentGas < 0) {
			startStation = i + 1;
			currentGas = 0;
		}
	}
	return totalGas >= 0 ? startStation : -1;
};