LeetCode 134. 加油站
题目描述
✅ 134. 加油站
题意分析
环形道路上有若干加油站。到达第
i站可获得gas[i]的油，从这里开到下一站需要消耗cost[i]；最后一站的下一站是第零站。油箱容量没有上限，但出发前是空的。选择一个起点，先在该站加油，再按顺序行驶，要求整个过程中油量不为负，并最终返回起点。返回起点下标；无法绕行一圈时返回
-1。总油量足够只是必要条件，还要保证选定起点不会在中途先缺油。
解法：贪心跳过失败区间
核心思路
[!blue]
令每站净收益为
diff = gas[i] - cost[i]。累加一段净收益，就是从该段起点空箱出发、依次加油并驶离各站后的剩余油量。total保存整圈净收益，tank保存当前候选起点start到当前站的净收益。若
tank在站点i第一次变为负数，说明从start无法驶过这里，并且[start, i]内的每个位置都不能作为起点。对其中任意j，从start到j - 1的净收益此前非负；从j到i的和等于已经为负的整段和，再减去这段非负前缀，只会更小。因此可以一次跳过整个失败区间，令start = i + 1并重置tank。为什么最后一个候选还能绕回开头？设
prefix[t]是前t站净收益之和，prefix[0] = 0。只有当前累计值比候选之前的前缀和更低时，才会发生失败并更换起点，所以最终start位于一个全局最小前缀和之后。从这个起点向后行驶，油量是
prefix[t] - prefix[start]，不会为负。越过末尾再走到开头部分时，油量是total + prefix[t] - prefix[start]；只要total >= 0，同样不会为负。因此总收益非负时，最终候选能完成整圈；总收益为负时，任何起点都无法补足整圈消耗。
解题步骤
- 初始化全局收益
total = 0、候选收益tank = 0、起点start = 0。- 逐站计算
gas[i] - cost[i]，同时加入total和tank。tank < 0时，排除当前候选到i的所有起点，将start设为i + 1，只把tank清零。- 扫描结束后，总收益为负则返回
-1，否则返回start。
代码实现
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)$，只维护候选起点、局部与全局收益；证明中的前缀数组无需实际创建。
关键点总结
[!green]
- 局部首次失败能排除整个候选区间，是一次扫描的依据。
- 最小前缀和后的起点能保证向后不缺油，总收益非负则保证绕回部分也不缺油。
tank随候选重置，total始终保存整圈信息，二者职责不同。- 恰好剩零油仍能合法到达下一站，只有负数才代表失败。
易错点总结
[!yellow]
- 只检查最后一段
tank非负，就宣称整圈可行，遗漏了此前失败区间留下的总亏损。- 更换候选时也把
total清零，失去判断整圈是否有解的依据。- 把新起点设为
i，仍然保留了已经证明不可能的站点；下一候选应为i + 1。- 用
tank <= 0排除候选，会把恰好用完油的合法状态也判为失败。- 只证明候选能走到数组末尾，没有解释环路返回开头的部分；还需要总收益与最小前缀的论证。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 918. 环形子数组的最大和 | 中等 | 两题都可丢弃累计和为负的前缀：本题据此排除一段失败起点，环形最大子数组中的 Kadane 状态也会从更优的新起点重新累计。 |