134. 加油站

🟠   🔖  贪心 数组  🔗 力扣 LeetCode

题目

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

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

Given two integer arrays gas and cost, return the starting gas station 's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique

Example 1:

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

Output: 3

Explanation:

Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4

Travel to station 4. Your tank = 4 - 1 + 5 = 8

Travel to station 0. Your tank = 8 - 2 + 1 = 7

Travel to station 1. Your tank = 7 - 3 + 2 = 6

Travel to station 2. Your tank = 6 - 4 + 3 = 5

Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.

Therefore, return 3 as the starting index.

Example 2:

Input: gas = [2,3,4], cost = [3,4,3]

Output: -1

Explanation:

You can't start at station 0 or 1, as there is not enough gas to travel to the next station.

Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4

Travel to station 0. Your tank = 4 - 3 + 2 = 3

Travel to station 1. Your tank = 3 - 3 + 3 = 3

You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.

Therefore, you can't travel around the circuit once no matter where you start.

Constraints:

• n == gas.length == cost.length
• 1 <= n <= 10^5
• 0 <= gas[i], cost[i] <= 10^4

题目大意

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

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

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

解题思路

这个问题可以通过一次遍历来解决，遍历过程中记录总加油量与总消耗量的差值，当找到总加油量 - 总消耗量最小值时，也即油最不够用的地方，说明需要在此之后的加油站出发，先补足不够的油，才能保证行驶一周，所以下一个加油站就是出发加油站。

1. 初始化变量 sum 表示总加油量与总消耗量的差值，变量 minSum 表示最小的差值，变量 start 表示起始索引，以及变量 n 表示加油站的数量。
2. 遍历每个加油站，计算总加油量与总消耗量的差值，并判断是否小于当前最小差值。如果是，则更新最小差值和起始索引。
3. 遍历结束后，如果总差值小于 0，说明无法绕一周，返回 -1；否则，返回起始索引。

复杂度分析

• 时间复杂度：O(n)，其中 n 是加油站的数量。一次遍历所有加油站。
• 空间复杂度：O(1)，只使用了常数个额外变量。

代码

/**
 * @param {number[]} gas
 * @param {number[]} cost
 * @return {number}
 */
var canCompleteCircuit = function (gas, cost) {
	let sum = 0,
		minSum = 0,
		start = 0,
		n = gas.length;
	for (let i = 0; i < n; i++) {
		sum += gas[i] - cost[i];
		if (sum < minSum) {
			minSum = sum;
			start = i + 1;
		}
	}
	if (sum < 0) {
		return -1;
	}
	return start == n ? 0 : start;
};

相关题目

题号	标题	题解	标签	难度
2202	K 次操作后最大化顶端元素		贪心 数组