解题思路
环形公路上 n 个加油站,从 i 到下一站净油量为 gasi−costi。要从某站空油箱出发绕一圈,中途油箱不能为负。有解时起点唯一。
- 先看总量:若 ∑gas<∑cost,整圈油不够,任何起点都失败,答案是 −1。
- 总量足够时一定存在唯一合法起点。从下标 0 扫到 n−1,维护当前油箱 tank。
- 一旦 tank<0,说明当前起点到站 i 这段永远补不回来,把起点改成 i+1,并把 tank 清零再继续。
- 扫完后留下的起点就是答案。因为更早的起点都会在第一次把 tank 打成负数的那段路上失败。
- 常见假解:从每个起点模拟整圈,复杂度 O(n2),在 n=105 时超时;选 gas−cost 最大的站当起点(净油多不代表后面填得上坑);只判断总量够就输出 0;把编号当成从 1 开始。