134. 加油站
题目描述
一条环形路上有 n 个加油站，编号 0 到 n - 1。在第 i 站可以加 gas[i] 升油；从第 i 站开到下一站（最后一站的下一站是 0）要花 cost[i] 升。
汽车油箱容量不限，出发时油箱是空的。选一个站出发，按编号递增的方向依次开过每一站，途中油量不能不够，最后回到出发站。
如果存在这样的出发站，返回它的编号；否则返回 -1。数据保证有解时解是唯一的。
示例 1
输入：gas = [1,2,3,4,5], cost = [3,4,5,1,2] 输出：3
解释：从 3 号站出发，油量依次为 4、8、7、6、5，恰好够开回 3 号站。
示例 2
输入：gas = [2,3,4], cost = [3,4,3] 输出：-1
解释：无论从哪站出发，都会在某段路上油不够。
数据范围
n == gas.length == cost.length1 <= n <= 10^50 <= gas[i], cost[i] <= 10^4- 答案若存在则唯一。
解题思路：贪心重置起点
令 diff[i] = gas[i] - cost[i]。若 sum(diff) < 0，油总量不够，一定无解。否则从 start = 0 开始累加 tank；一旦 tank < 0，说明从 start 到 i 之间的任何站出发都到不了 i+1，直接把起点改为 i + 1、tank 清零。一遍扫完后 start 就是答案。
为什么正确
当前 tank 是从 start 出发到 i+1 时的剩油量，且 start 之前的站都已被排除。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
起点要重置为 i + 1 而不是 start + 1；最后要用 total 判定是否有解，不能只看 tank。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
total = 0
tank = 0
start = 0
for i in range(len(gas)):
diff = gas[i] - cost[i]
total += diff
tank += diff
if tank < 0:
start = i + 1
tank = 0
return start if total >= 0 else -1class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int total = 0;
int tank = 0;
int start = 0;
for (int i = 0; i < gas.length; i++) {
int diff = gas[i] - cost[i];
total += diff;
tank += diff;
if (tank < 0) {
start = i + 1;
tank = 0;
}
}
return total >= 0 ? start : -1;
}
}class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int total = 0;
int tank = 0;
int start = 0;
for (int i = 0; i < (int)gas.size(); i++) {
int diff = gas[i] - cost[i];
total += diff;
tank += diff;
if (tank < 0) {
start = i + 1;
tank = 0;
}
}
return total >= 0 ? start : -1;
}
};func canCompleteCircuit(gas []int, cost []int) int {
total := 0
tank := 0
start := 0
for i := 0; i < len(gas); i++ {
diff := gas[i] - cost[i]
total += diff
tank += diff
if tank < 0 {
start = i + 1
tank = 0
}
}
if total >= 0 {
return start
}
return -1
}var canCompleteCircuit = function(gas, cost) {
let total = 0;
let tank = 0;
let start = 0;
for (let i = 0; i < gas.length; i++) {
const diff = gas[i] - cost[i];
total += diff;
tank += diff;
if (tank < 0) {
start = i + 1;
tank = 0;
}
}
return total >= 0 ? start : -1;
};function canCompleteCircuit(gas: number[], cost: number[]): number {
let total = 0;
let tank = 0;
let start = 0;
for (let i = 0; i < gas.length; i++) {
const diff = gas[i] - cost[i];
total += diff;
tank += diff;
if (tank < 0) {
start = i + 1;
tank = 0;
}
}
return total >= 0 ? start : -1;
}其他解法
两种解法都是一次遍历；贪心从“油量为负就换起点”局部推理，前缀和法从“整条曲线的最低点”全局推理。
解法 2：前缀和最低点 时间 O(n)，空间 O(1)
把 gas[i] - cost[i] 的前缀和看成油量曲线，并把起点前的前缀和记为 0。若总和小于 0，无论从哪里出发都走不完一圈。否则从曲线最低点的下一站出发，之后每一点都不低于起点，油量始终非负。
结论可以用图像直接看出，证明简洁。代码与贪心解法很像，但理解角度是全局最小值。
from typing import List
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
prefix = 0
low = 0
start = 0
for i in range(len(gas)):
prefix += gas[i] - cost[i]
if prefix < low:
low = prefix
start = i + 1
return start if prefix >= 0 else -1class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int prefix = 0, low = 0, start = 0;
for (int i = 0; i < gas.length; i++) {
prefix += gas[i] - cost[i];
if (prefix < low) {
low = prefix;
start = i + 1;
}
}
return prefix >= 0 ? start : -1;
}
}class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int prefix = 0, low = 0, start = 0;
for (int i = 0; i < (int)gas.size(); i++) {
prefix += gas[i] - cost[i];
if (prefix < low) {
low = prefix;
start = i + 1;
}
}
return prefix >= 0 ? start : -1;
}
};func canCompleteCircuit(gas []int, cost []int) int {
prefix, low, start := 0, 0, 0
for i := range gas {
prefix += gas[i] - cost[i]
if prefix < low {
low = prefix
start = i + 1
}
}
if prefix < 0 {
return -1
}
return start
}var canCompleteCircuit = function(gas, cost) {
let prefix = 0, low = 0, start = 0;
for (let i = 0; i < gas.length; i++) {
prefix += gas[i] - cost[i];
if (prefix < low) {
low = prefix;
start = i + 1;
}
}
return prefix >= 0 ? start : -1;
};function canCompleteCircuit(gas: number[], cost: number[]): number {
let prefix = 0, low = 0, start = 0;
for (let i = 0; i < gas.length; i++) {
prefix += gas[i] - cost[i];
if (prefix < low) {
low = prefix;
start = i + 1;
}
}
return prefix >= 0 ? start : -1;
}