题目描述
环形路上 n 个加油站，gas[i] 是油量、cost[i] 是到下一站的耗油。求能跑完一圈的出发站，不行返回 −1。
gas = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
输出 = 3
思路解析
如果所有 net 之和 < 0，那怎么都跑不完，返回 −1。否则从 0 出发累加 net，一旦油箱变负，说明这一段没法当起点，就把起点跳到 i+1、油箱清零，继续。
假设从 a 出发一路顺到 b 时油箱第一次变负：那 a 不行（没撑到 b）；a 和 b 之间任意一站 c 当起点也不行——从 a 到 c 这段油箱一直 ≥0，少了这段油，c 出发时只会更少，照样到不了 b。所以 a…b 这一整段都能直接排除，起点跳到 b 的下一站。这就是它能 O(n) 的原因。
先看总量：net 之和 ≥ 0，说明存在可行起点。接下来一遍扫描找它。
i=0 · 油箱负：从 0 出发，到下一站油箱 −2 < 0，抛锚。0 不能当起点，把起点（紫 l）跳到 1，油箱清零。
i=1 · 油箱负：从 1 出发也立刻负，起点跳到 2。
i=2 · 油箱负：从 2 出发还是负，起点跳到 3。
i=3 · 油箱 +3：从 3 出发，到 4 油箱 +3，没抛锚，起点保持 3。
i=4 · 油箱 +6：继续，油箱 6，全程没负。扫描结束。
结果：因为总油 ≥ 总耗（有解），最后留下的起点 3 就是答案。
不傻试每个起点，而是利用「跑到这里就负了」这条失败信息，一次性跳过整段不可能的起点——这就是贪心的剪枝，O(n²) 暴力因此降到 O(n)。
参考代码（Python）
Python
1if sum(gas) < sum(cost): return -1 # 总量不够，无解
2tank, start = 0, 0
3for i in range(n):
4 tank += gas[i] - cost[i]
5 if tank < 0: # 这段当不了起点
6 start = i + 1 # 起点跳到下一站
7 tank = 0 # 油箱清零
8return start复杂度分析
- 时间复杂度：O(n) —— 一遍扫描
- 空间复杂度：O(1) —— 两个变量
套路模板
骨架就是「全局量判可行 + 局部量变负就重置」。最大子数组和（LC53）只把 run 换成「当前最大和」、start 换成记录答案，几乎一模一样。
Python
1# 一遍扫描里「局部累计变负就丢弃重来」的通用骨架
2total, run, start = 0, 0, 0
3for i in range(n):
4 total += val[i] # 全局量：判可行 / 求总和
5 run += val[i] # 局部量：当前这一段
6 if run < 0: # 这一段废了
7 run, start = 0, i + 1 # 清零，起点跳到下一站易错点
- ❌ 不先判总量直接找起点 → ✅ 先 sum(gas) < sum(cost) 判 -1（总量不够时再找也没有答案）
- ❌ 油箱负了不清零 → ✅ start=i+1 后 tank 要清零（新起点要从空油箱重新算）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。