LeetCode 134. 加油站
目录
题目描述
✅ 134. 加油站
题意分析
环形公路上有
n个加油站，在第i站可以加到gas[i]升油，从第i站开到第i + 1站要消耗cost[i]升油。油箱容量无限，出发时油箱是空的，问能否找到一个出发点顺时针绕行一整圈回到原点，能则返回该出发点下标，不能则返回 -1。关键约束是「油箱不能为负」：走到任意一站时累计的加油量必须不小于累计的消耗量，中途一旦透支就算失败。换个说法，把每站的净收益记作
diff[i] = gas[i] - cost[i]，那么从起点开始的每一段前缀和都必须非负。题目额外保证：如果存在解，则解唯一。这条保证很有用，意味着不必担心「找到的是不是字典序最小的那个」，只要找出一个可行起点即可。
数组长度可达 $10^5$，说明对每个起点各模拟一圈的 $O(n^2)$ 做法会超时。边界上要留意
n = 1的情形：只有一站时，gas[0] >= cost[0]就返回 0，否则返回 -1；另外gas与cost中的元素都非负，但diff可正可负。
解法：贪心跳过失败区间
核心思路
把每站的净收益记为
diff[i] = gas[i] - cost[i]。绕行一圈后的总油量与起点无关，因此total = sum(diff)若小于 0，一定无解；但total >= 0只说明整体够用，还要找到中途不会透支的起点。维护当前候选起点
start和从它出发的剩余油量tank。若扫描到i时tank < 0，不仅start失败，start到i的所有位置都失败：对任意中间位置k，从start到k-1的累计和非负，而从start到i的累计和为负，两者相减可知从k到i也为负。因此下一候选可以直接跳到i+1。循环不变量是：
start之前的候选都已排除，tank是从start到当前位置的净收益，且重置后每个已扫描前缀都非负。每次重置还相当于把start放到全局前缀和的新最低点之后。设P[j]是从 0 到j的前缀和，则绕回任意j < start时的油量为total - P[start-1] + P[j]；因为P[start-1]是此前最小值且total >= 0，该值也非负，所以最终候选能走完整圈。
解题步骤
- 初始化
total = 0、tank = 0、start = 0。- 遍历每站，将
gas[i] - cost[i]同时累加到total和tank。- 若
tank < 0，排除[start, i]，令start = i + 1、tank = 0。- 扫描结束后，
total >= 0返回start，否则返回 -1。例如
gas = [1,2,3,4,5]、cost = [3,4,5,1,2]，净收益为[-2,-2,-2,3,3]。前三站分别使候选起点跳到 1、2、3；从 3 开始累计油量始终非负，且总和为 0，因此答案是 3。
代码实现
class 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) {
// 当前起点到 i 之间的所有位置都无法作为起点。
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
}
复杂度分析
- 时间复杂度：$O(n)$，每个加油站只处理一次。
- 空间复杂度：$O(1)$，只维护三个标量。
关键点总结
total判断是否有解，tank判断当前候选是否仍可行，两者职责不同。- 一次透支可以排除整段候选，这是线性贪心成立的关键证明。
- 透支条件是严格小于 0；油量恰好为 0 仍然合法。
- 面试口述顺序：先给总量必要条件，再证明失败区间可整体跳过，最后说明总量非负时剩余候选成立。
易错点总结
- 只看最后一段的
tank会把无解误判为有解；gas=[2,3,4]、cost=[3,4,3]的total=-1，应返回 -1。- 透支后将
start设为i会保留已经失败的位置，正确的新起点是i+1。- 重置
tank时不能重置total，否则会丢失整圈是否可行的信息。- 使用
tank <= 0会误排除油量恰好为 0 的合法状态；gas=[1]、cost=[1]应返回 0。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 55. 跳跃游戏 | 中等 | 同为可行性贪心，但维护的是「能到达的最远位置」而非累计余量 |
| 45. 跳跃游戏 II | 中等 | 从判断可行升级为求最少步数，需要按层维护当前跳跃的边界 |
| 122. 买卖股票的最佳时机 II | 中等 | 同样先转成差值数组，但目标是把所有正差值累加而非寻找起点 |
| 42. 接雨水 | 困难 | 同为一次扫描中维护前缀极值的贪心，难点在左右两侧同时约束 |
| 11. 盛最多水的容器 | 中等 | 贪心的合法性同样靠「移动短板不会错过最优解」的反证来支撑 |