在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
思路分析
- 遍历每个加油站，计算从当前加油站出发，到下一个加油站时的剩余油量（即
gas[i] - cost[i]），并将其累加到总剩余油量total中。 - 同时，用一个变量
current来记录从某个假设的起始加油站出发到当前加油站时的剩余油量。 - 如果在某一个加油站
i处，current的值小于 0，说明从之前假设的起始加油站出发无法到达当前加油站，此时将current重置为 0，并将起始加油站的候选值设为i + 1。 - 遍历完所有加油站后，如果
total大于等于 0，说明总油量足够绕环路行驶一周，返回记录的起始加油站的候选值；否则返回 -1，表示无法绕环路行驶一周。
方法一
代码实现
function canCompleteCircuit(gas: number[], cost: number[]): number {const n = gas.length;let total = 0;let current = 0;let start = 0;for (let i = 0; i < n; i++) {const diff = gas[i] - cost[i];total += diff;current += diff;if (current < 0) {start = i + 1;current = 0;}}return total >= 0? start : -1;
}// 示例调用
const gas = [1, 2, 3, 4, 5];
const cost = [3, 4, 5, 1, 2];
const result = canCompleteCircuit(gas, cost);
console.log("可以绕环路行驶一周的出发加油站编号:", result);
代码解释
- 初始化变量：
n表示加油站的数量。total用于记录总的剩余油量，初始化为 0。current用于记录从某个假设的起始加油站出发到当前加油站时的剩余油量，初始化为 0。start用于记录可能的起始加油站编号，初始化为 0。
- 遍历加油站：
- 对于每个加油站
i，计算从该加油站到下一个加油站的剩余油量diff = gas[i] - cost[i]。 - 将
diff累加到total中，同时也累加到current中。 - 如果
current小于 0，说明从之前假设的起始加油站出发无法到达当前加油站，将start更新为i + 1，并将current重置为 0。
- 对于每个加油站
- 判断结果：
- 遍历结束后，如果
total大于等于 0，说明总油量足够绕环路行驶一周，返回start；否则返回 -1，表示无法绕环路行驶一周。
- 遍历结束后，如果
复杂度分析
- 时间复杂度：O(n)，其中
n是加油站的数量。因为只需要遍历一次gas和cost数组。 - 空间复杂度：O(1)，只使用了常数级的额外变量。
这种贪心算法的思路简单高效，能够在一次遍历中找到合适的起始加油站或者判断出无法绕环路行驶一周的情况。
方法二
除了贪心算法，还可以使用暴力枚举的方法来解决这个问题。暴力枚举的思路很直接，就是从每一个加油站出发，模拟汽车的行驶过程，判断是否能够绕环路行驶一周。
以下是使用 TypeScript 实现的暴力枚举代码：
function canCompleteCircuit(gas: number[], cost: number[]): number {const n = gas.length;for (let start = 0; start < n; start++) {let currentGas = 0;let i = start;let flag = true;do {currentGas += gas[i];currentGas -= cost[i];if (currentGas < 0) {flag = false;break;}i = (i + 1) % n;} while (i!== start);if (flag) {return start;}}return -1;
}// 示例调用
const gas = [1, 2, 3, 4, 5];
const cost = [3, 4, 5, 1, 2];
const result = canCompleteCircuit(gas, cost);
console.log("可以绕环路行驶一周的出发加油站编号:", result);
代码解释
- 外层循环枚举起始加油站：通过
for循环，从索引0到n - 1依次枚举每一个加油站作为起始加油站，这里的n是加油站的数量。 - 模拟行驶过程：对于每一个选定的起始加油站
start，初始化当前油量currentGas为0，并设置一个标志位flag为true，用于标记是否能够绕环路行驶一周。然后进入一个do-while循环，模拟汽车从当前加油站出发，依次前往下一个加油站的过程。- 在每次循环中，先将当前加油站的油量
gas[i]加入到currentGas中，再减去行驶到下一个加油站所需的油量cost[i]。 - 如果
currentGas小于0，说明在当前加油站油量不足，无法继续行驶，将flag设置为false并跳出循环。 - 更新
i为下一个加油站的索引，通过(i + 1) % n实现环形的索引处理。 - 循环继续的条件是
i不等于start，即还没有绕环路行驶一周。
- 在每次循环中，先将当前加油站的油量
- 判断结果：如果在模拟行驶过程中
flag始终为true，说明从当前起始加油站出发可以绕环路行驶一周，返回当前起始加油站的索引start；如果循环结束后没有找到这样的起始加油站，则返回-1。
复杂度分析
- 时间复杂度：O(n^2)，其中
n是加油站的数量。外层循环枚举每个加油站作为起始点，时间复杂度为O(n) ，对于每个起始点，模拟行驶过程最多需要遍历一圈加油站，时间复杂度也为O(n) ，所以总的时间复杂度为O(n^2) 。 - 空间复杂度：O(1)，只使用了常数级的额外变量，如
currentGas、i、flag等。
暴力枚举法虽然简单易懂，但时间复杂度较高，相比之下贪心算法在效率上更有优势。
