题目描述
环形路上 n 个加油站，gas[i] 是这站的油量、cost[i] 是开到下一站的耗油。求能跑完一圈的出发站下标，跑不完返回 −1。
思路解析
最直接是枚举每个起点，从它出发模拟跑一圈、看油箱会不会变负。n 个起点、每个跑 n 步，O(n²)。其实一次失败能透露很多信息，不必每个起点从头再试。
关键招：若 sum(net) 小于 0，怎么都跑不完，返回 −1。否则从 0 出发累加 net，一旦油箱 tank 变负，说明从当前起点到这里这一整段都当不了起点——因为这段里油箱一直 ≥0，去掉它前面任意一站当起点只会油更少、更到不了这里。所以起点直接跳到 i+1、tank 清零。一遍扫描即可，这就是它 O(n) 的原因。
先看总量：先算 net 总和：等于 0，≥ 0，说明存在可行起点。接下来一遍扫描把它找出来。
起点就位：油箱 tank 清零，候选起点 start=0(紫 l 标起点)。开始累加 net。
i=0 · 油箱变负 → 起点跳到 1：负例分支：从 0 出发，tank = −2 小于 0，抛锚。0 当不了起点，把 start 跳到 1、tank 清零重新算。
i=1 · 又变负 → 起点跳到 2：从 1 出发也立刻 tank = −2 小于 0，start 跳到 2。下标 0 已被整段排除(变灰)。
i=2 · 还是负 → 起点跳到 3：从 2 出发仍是 tank = −2，start 跳到 3。前三站 [0,1,2] 整段都被排除了。
i=3 · 油箱 +3 → 撑住：从 3 出发，tank = 3 ≥ 0，没抛锚，start 保持 3，继续往后开。
i=4 · 油箱 +6 → 顺利：再往后 tank = 6 ≥ 0，从 start=3 起油箱一路没变负。扫描到末尾结束。
结果：因为总油 ≥ 总耗(第一步已确认有解)，扫描结束时留下的起点 3 就是唯一可行出发站。
不傻试每个起点，而是利用「跑到这里就变负」这条失败信息，一次性跳过整段不可能的起点——这就是贪心的剪枝，把 O(n²) 暴力降到 O(n)。
参考代码（Python）
1if sum(gas) < sum(cost):
2 return -1 # 总量不够，无解
3tank, start = 0, 0
4for i in range(len(gas)):
5 tank += gas[i] - cost[i] # 累加这一站的净收益
6 if tank < 0: # 这一段当不了起点
7 start = i + 1 # 起点跳到下一站
8 tank = 0 # 油箱清零重算
9return start复杂度分析
- 时间复杂度：O(n) —— 总量预判扫一遍、找起点再扫一遍，都是线性
- 空间复杂度：O(1) —— 只用 tank、start 两个变量
套路模板
骨架就是「全局量判可行 + 局部量变负就重置」。最大子数组和(LC53)只把 run 换成「当前最大和」、start 换成记录答案，几乎一模一样。
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 一定可行）
- 错误写法：油箱变负后忘了把 tank 清零 → 正确写法：start=i+1 后 tank 必须清零（新起点要从空油箱重新算，残留的负油箱会污染下一段的累加，导致起点判断全错）
- 错误写法：用嵌套循环对每个 start 重新跑一圈验证 → 正确写法：一遍扫描即可，不回头重试（本题精髓就是「失败一次排除整段」，再套一层模拟就退化回 O(n²)，白白丢掉这条剪枝）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。