最低加油次数

因为加油站只要开过去就永远能用(它的油一直在那等你),所以不必当场决定。攒着,等卡住了再补——而且每次都补油最多的那个,这样补的次数一定最少。

盯住下面三样怎么变:车的油量 fuel(能开多远 = 当前油量)、指针 ptr(沿路把开过的加油站油量记进堆)、大根堆(堆顶永远是攒下的最大那桶油)。

第 0 步 · 把加油站按位置排在路上：加油站本来就按位置升序给好。车从 0 出发,起步油 10——也就是最远只能开到位置 10。最后一格是终点 100。指针 ptr 沿路往右,把够得着的加油站油量记进堆。

第 1 段 · 油 10 能开到哪?：起步油 10,车最远开到位置 10,正好够到 s0。把它的油量 60 记进堆(先不加,攒着)。再看 s1 在位置 20,油 10 开不到,指针先停下。

第 1 段 · 油 10 用尽,卡在 s0 处：起步油 10 全烧光,车只到位置 10 就开不动了,离终点 100 还差得远(后面的站都够不着,变灰)。但堆里攒着 s0 的油 60,该取出来加上了。

s0 记进堆 · 油量 60：经过 s0,把它的油量 60 记进堆(堆 = 攒下还没用的油)。堆顶永远是攒下的里最大的那桶。现在油 10 到不了终点 100,也开不到下一站,必须从堆里取油。

第 1 次加油 · 取堆顶最大的油 60：油不够,就从堆顶取攒下最大的那桶 60 加进油箱,油从 10 涨到 70,加油次数 +1。油变多了,原本开不到的加油站这下都够得着——回去推指针继续记账。

油 70 上路 · 一下能开到位置 70：油涨到 70,车一口气能开到位置 70——绿勾标出的 s1、s2、s3 全在射程内,接下来要把它们的油都记进堆。但终点 100 还在 70 之外,记完仍得再取一次油。

第 2 段 · 油 70 能开到哪?：油涨到 70,车最远能开到位置 70。指针往右推:s1 在 20,够得着,油量 30 记进堆。s0 已用过(灰)。70 还能开更远,接着看下一个。

s1 记进堆 · 油量 30：s1 的油 30 记进堆。但记账阶段还没结束——油 70 也开得到位置 30 的 s2,先把沿途够得着的全记进来,再决定要不要取油。

第 2 段续 · 油 70 还够得着 s2：油 70 也开得到 s2(位置 30),油量 30 一起记进堆。这一段一口气记了两个站。再往右看 s3 在位置 60,油 70 也够——继续推。

s2 记进堆①·新元素先挂到堆底：入堆分两步。第一步:新油量 30 先塞到堆的最末尾。它和父亲 30 一样大,没有「比父亲大」,所以不违反大根堆规矩,不用往上冒。

s2 记进堆②·已就位,堆合法：s2 的 30 就位了——它不比父亲大,留在堆底当孩子,堆依然合法。现在堆里攒了两桶 30。油 70 还能开到 s3,先把它也记进来,再决定取哪桶。

第 2 段续 · 油 70 还够得着 s3：油 70 还够得着 s3(位置 60),油量 40 记进堆。指针走到加油站末尾,沿途能记的全记完了。但油 70 仍开不到终点 100,所以还得取油。

s3 记进堆①·新元素挂到堆底：新油量 40 先挂到堆的最末尾,它的父亲是堆顶的 30。40 比父亲 30 大,违反了「大根堆父亲最大」的规矩,所以下一帧要让 40 往上冒。

s3 记进堆②·上浮:40 比父亲 30 大：第二步「上浮」:新来的 40 和父亲 30 比,40 更大就交换、一路往上冒,直到比父亲小或到顶。这里 40 一步就冒到了堆顶,原来的 30 沉下去当孩子。这就是堆维持「堆顶最大」的内部动作。

记账完毕 · 油 70 仍卡在终点前：沿途的加油站全记进堆了(s1、s2、s3),指针到头。可油 70 还是到不了终点 100(终点变灰)。堆里攒着 30、30、40 三桶,该取最大的 40 加上。

第 2 次加油①·拿走堆顶 + 末尾补位：取堆顶分两步。第一步:把堆顶 40 拿走做掉(加进油箱),再把末尾的 30 搬到堆顶补空。现在堆顶临时是 30,接下来要让它和孩子比、必要时一路「下沉」。

第 2 次加油②·30 已就位 + 油到终点：补到顶的 30 不比孩子小,停在顶上,堆依然合法。第一步拿走的 40 加进油箱,油从 70 涨到 110,已经 ≥ 100,到终点了!加油次数 = 2。堆里剩的两桶 30 没机会用了。

到达终点 · 总共加了 2 次油：整道题就是这个循环:能开多远就把沿途加油站油量记进堆,开不动了就取堆顶最大那桶。绿勾标出真正加油的两个站(s0 的 60、s3 的 40),油一路 10 → 70 → 110,答案 2,和手算一致。

别一经过加油站就加(会浪费次数),也别只挑近的加——决定加哪桶的永远是油量大小。攒着,卡住再取最大,这就是「反悔型贪心」:先记下所有可能,等需要时挑最优的兑现。

认出这类题的信号:① 候选随某个单调量(位置/本金/时间)逐步「解锁」;② 每次只需要候选里的最大或最小。一旦命中,就是「排序解锁 + 堆取极值」,502 / 630 都是它。

提速对比：核心提速:用大根堆替代每次卡住重扫。每个加油站一生只进堆一次、出堆一次,取最大油只要 O(log n),不再做重复劳动。

易错实演 · 卡住又堆空 → 返回 -1：如果油不够开到任何还没记的加油站,堆又是空的(没攒下任何油可取),就说明永远到不了终点,必须返回 -1,不能硬去取空堆。

边界三连：边界都围绕「一次都不用加」和「一开始就到不了」:起步油够就返回 0,没油可攒就返回 -1。

面试追问：面试官常追问 Python 大根堆的实现、DP 的另解、以及大数据下的溢出处理。