加油站

最直接是枚举每个起点，从它出发模拟跑一圈、看油箱会不会变负。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)。

边界三连：三种边界先想清楚。

面试官常追问：三个高频追问，答法记牢。