加油站 图解题解
这道题到底在问什么
- gas
- [1, 2, 3, 4, 5]
- cost
- [3, 4, 5, 1, 2]
- 输出
- 3
先想最直接的笨办法
最直接是枚举每个起点，从它出发模拟跑一圈、看油箱会不会变负。n 个起点、每个跑 n 步，O(n²)。其实一次失败能透露很多信息，不必每个起点从头再试。（动画第 3 步）
最优解：一步一步想明白
- 3最直接是枚举每个起点，从它出发模拟跑一圈、看油箱会不会变负。n 个起点、每个跑 n 步，O(n²)。其实一次失败能透露很多信息，不必每个起点从头再试。
- 4关键招：若 sum(net) 小于 0，怎么都跑不完，返回 −1。否则从 0 出发累加 net，一旦油箱 tank 变负，说明从当前起点到这里这一整段都当不了起点——因为这段里油箱一直 ≥0，去掉它前面任意一站当起点只会油更少、更到不了这里。所以起点直接跳到 i+1、tank 清零。一遍扫描即可，这就是它 O(n) 的原因。
- 5sum(net) = 0 ≥ 0先算 net 总和：等于 0，≥ 0，说明存在可行起点。接下来一遍扫描把它找出来。
- 6tank=0, start=0油箱 tank 清零，候选起点 start=0(紫 l 标起点)。开始累加 net。
- 7tank=−2 小于 0负例分支：从 0 出发，tank = −2 小于 0，抛锚。0 当不了起点，把 start 跳到 1、tank 清零重新算。
- 8tank=−2 小于 0从 1 出发也立刻 tank = −2 小于 0，start 跳到 2。下标 0 已被整段排除(变灰)。
- 9tank=−2 小于 0从 2 出发仍是 tank = −2，start 跳到 3。前三站 [0,1,2] 整段都被排除了。
- 10tank=3 ≥ 0从 3 出发，tank = 3 ≥ 0，没抛锚，start 保持 3，继续往后开。
- 11tank=6 ≥ 0再往后 tank = 6 ≥ 0，从 start=3 起油箱一路没变负。扫描到末尾结束。
- 12出发站 = 3因为总油 ≥ 总耗(第一步已确认有解)，扫描结束时留下的起点 3 就是唯一可行出发站。
- 15不傻试每个起点，而是利用「跑到这里就变负」这条失败信息，一次性跳过整段不可能的起点——这就是贪心的剪枝，把 O(n²) 暴力降到 O(n)。
⚠️ 容易写错的地方
✗ 错：不先判总量就直接找起点
✓ 对：先用 sum(gas) 小于 sum(cost) 判 −1
总油不够时本就无解，跳过预判会把扫描留下的起点误当答案返回。只有总量足够，这套贪心才保证留下的 start 一定可行
✗ 错：油箱变负后忘了把 tank 清零
✓ 对：start=i+1 后 tank 必须清零
新起点要从空油箱重新算，残留的负油箱会污染下一段的累加，导致起点判断全错
✗ 错：用嵌套循环对每个 start 重新跑一圈验证
✓ 对：一遍扫描即可，不回头重试
本题精髓就是「失败一次排除整段」，再套一层模拟就退化回 O(n²)，白白丢掉这条剪枝
完整代码（Python / C++ / Java）
Python
class Solution:
def canCompleteCircuit(self, gas, cost):
total = tank = start = 0
for i in range(len(gas)):
net = gas[i] - cost[i]
total += net
tank += net
if tank < 0: # 从 start 跑不到 i+1
start = i + 1 # 起点跳到 i+1
tank = 0
return start if total >= 0 else -1 # 总净油≥0 才有解C++
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int total = 0, tank = 0, start = 0;
for (int i = 0; i < gas.size(); i++) {
int net = gas[i] - cost[i];
total += net; tank += net;
if (tank < 0) { start = i + 1; tank = 0; } // 起点跳到 i+1
}
return total >= 0 ? start : -1;
}
};Java
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int total = 0, tank = 0, start = 0;
for (int i = 0; i < gas.length; i++) {
int net = gas[i] - cost[i];
total += net; tank += net;
if (tank < 0) { start = i + 1; tank = 0; } // 起点跳到 i+1
}
return total >= 0 ? start : -1;
}
}套路模板 · 贪心扫描「跑和变负就重置」（背下来）
# 一遍扫描里「局部累计变负就丢弃重来」的通用骨架
total, run, start = 0, 0, 0
for i in range(n):
total += val[i] # 全局量：判可行 / 求总和
run += val[i] # 局部量：当前这一段
if run < 0: # 这一段废了
run, start = 0, i + 1 # 清零，起点跳到下一站复杂度
时间复杂度
O(n)
一遍扫描:total 累计净油判可行、tank 同时定起点,只走一趟,线性
空间复杂度
O(1)
只用 tank、start 两个变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 加油站 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
核心思路是什么？+
贪心一遍：tank 记从当前候选起点跑到 i 的累计净油；tank＜0 说明 start..i 都当不了起点，start 跳到 i+1、tank 清零。最后总净油≥0，留下的 start 就是答案。
为什么这样贪心是对的？+
两条：① 总油≥总耗必有解；② 从 start 跑到 i 变负，则 start..i 之间任何点起步只会更早变负，可整段跳过。一遍扫描即得唯一起点。
复杂度多少？+
一遍扫描 O(n)；只用 total/tank/start 几个变量 O(1)。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。