1. 题目本质与解题方向拆解
1.1 先把题目翻译成人话
LeetCode 871题，Minimum Number of Refueling Stops，题目描述其实非常直白：你开一辆车从起点去终点，起点距离终点有 target 英里，车油箱一开始有 startFuel 加仑油。沿途有若干个加油站，每个加油站有一个位置和一个油量。假设这辆车每加仑油可以跑1英里，问你最少需要加几次油才能到达终点。如果中途某个加油站都到不了，那就返回 -1。
这个题在 LeetCode 上被标记为 Hard，但本质其实是一道贪心 + 优先队列的经典题。我第一次做的时候用了 DP，虽然能过，但时间和空间都不是最优。后来把思路切换到贪心之后，代码量直接少了一半，性能也上去了。这道题在面试里出现的频率不低，尤其是做基础设施、网络传输、任务调度这类方向的岗位，非常喜欢拿这种“资源不够就沿途补充”的模型来考候选人。
1.2 为什么这题值得花时间吃透
这题表面上是“汽车加油”，但换个马甲，它就是一堆现实问题的抽象：
- 网络传输中，数据包每经过一个节点消耗一定的带宽预算，节点可以补充预算，问最少需要多少补充节点。
- 服务器部署中，任务从起点跑到终点，每个中间节点能补资源，问最少部署几个资源点。
- 项目管理中，你手上有初始预算，每个里程碑可以“报销”一部分费用，问最少找几个里程碑报销才能撑到项目结束。
也就是说，这个模型是资源受限场景下的“最少补给点”问题，搞懂了这题，很多类似的问题你就都能一眼看穿。后面我会用最直白的方式把贪心 + 堆的思路掰开揉碎，再对比 DP 写法，最后附上我自己实际跑测试时的几个坑。
2. 两种主流解法：DP 与贪心的对比分析
2.1 DP 思路：直观但效率一般
先说 DP。定义一个 dp[i] 表示“加了 i 次油之后，最多能跑多远”。初始化 dp[0] = startFuel，因为一次油都不加，就靠初始油量跑。
然后遍历每一个加油站，对于每个加油站 station，我们从大到小更新 dp 数组：
def minRefuelStops(target, startFuel, stations): n = len(stations) dp = [0] * (n + 1) dp[0] = startFuel for i in range(n): for j in range(i, -1, -1): if dp[j] >= stations[i][0]: dp[j + 1] = max(dp[j + 1], dp[j] + stations[i][1]) for i in range(n + 1): if dp[i] >= target: return i return -1这个思路的核心是：只有在当前油量够得着这个加油站的时候，我们才考虑“在这个站加油”这个动作。从大到小更新是为了防止同一个加油站在同一轮里被用多次，这是背包问题的经典套路。
DP 的优点是思路很直观，不用想什么“后悔”机制，代码也不容易写错。缺点是时间复杂度和空间复杂度都是 O(n²)，当加油站数量到几千个的时候，性能就比较吃紧了。我实测 1000 个站点的数据，Python 版本大概要跑到 200ms 左右，虽然 LeetCode 上能过，但显然不是最优解。
2.2 贪心思路：迟付代价最小化
贪心的思路就完全不同了。我们不提前决定在哪加油，而是先往前开，开到一个地方发现“不行，油不够到下一个站或终点了”，才在沿途经过的加油站里选一个油量最大的来加。
这个“经过但不急着加，等没油了再回头选最划算的”策略，本质上是把决策延后，保证每一次加油都是“被迫的”，从而让加油次数最少。举个生活化的例子：你出差报销额度有限，每到一个城市都有供应商可以请你吃饭，但你不知道后面哪顿饭更贵，干脆先不吃，等饿得不行的时候，在已经路过的城市里挑一家最贵的吃，这样你吃“最划算”的顿数最少。
具体实现需要借助优先队列（最大堆）：
import heapq def minRefuelStops(target, startFuel, stations): # 在终点也放一个“加油站”，方便统一判断 stations.append([target, 0]) fuel = startFuel heap = [] # 存放沿途经过的加油站的油量，最大堆（用负数实现） ans = 0 prev = 0 for pos, gas in stations: fuel -= pos - prev # 油不够到当前点，就从堆里挑一个最大的油量加 while fuel < 0 and heap: fuel += -heapq.heappop(heap) ans += 1 # 如果堆都空了还是不够，说明到不了这里 if fuel < 0: return -1 # 把这个站的油量加入堆，供后面使用 heapq.heappush(heap, -gas) prev = pos return ans这段代码看起来非常简洁，但里面的细节不少，下面我逐行拆一下。
3. 贪心解法的关键细节与操作要点
3.1 为什么要在 stations 末尾追加终点
很多人第一次写这题的时候，会在主循环结束之后单独判断一次“当前油够不够到终点”。这样写不是不行，但会让逻辑多一个分支，而且容易漏判。
把终点当成一个油量为 0 的“虚拟加油站”追加到数组末尾，好处是整个判断过程可以统一到循环里。当遍历到终点时，fuel 会先减去从上一个站到终点的距离，如果此时 fuel 小于 0，就进入 while 循环加油；如果燃料耗尽都补不够，就返回 -1。如果 fuel 恰好大于等于 0，说明不需要再加油，循环自然结束，ans 就是答案。
这个技巧在面试里可以主动提一嘴，能体现你对“边界情况统一处理”的敏感度。
3.2 堆里存的是什么？为什么用负数
Python 的 heapq 默认是最小堆，也就是每次 pop 出来的是堆里最小的元素。但我们需要每次拿最大油量，所以有两种做法：
- 存负数，pop 出来再加负号还原。
- 用自定义对象，重载比较运算符。
绝大多数情况下，第一种更简洁高效。这里我强调一个细节：堆里存的是“经过的加油站的可加油量”，而不是“剩余里程”。这是很多新手最容易搞混的地方。我们要最大化的是“还能补多少油”，不是“下次还能跑多远”，因为每次补完油之后，你的续航能力会实时变化，而加油量是一个客观属性。
3.3 while 循环里的 fuel 变化逻辑
每次加油，我们执行的是fuel += -heapq.heappop(heap)，同时 ans 加 1。这个逻辑要配合循环条件while fuel < 0 and heap来理解。
- 如果 fuel 只是少了一点点，比如从 0 变成 -1，那么加一个油量大的站，一次就能补回正值，循环结束。
- 如果 fuel 负得很多，比如 -100，而堆里最大的油只有 30，那么加一次不够，就要继续 pop 下一个，直到 fuel 非负或堆空了为止。
这里有一个容易出错的地方：加油是在当前站点位置发生的，还是在之前某个位置发生的？答案是：当前位置。因为我们要赶到“当前这个点”（可能是某加油站，也可能是终点）时发现油不够了，此时我们已经路过了前面所有加油站，所以它们都已经进入堆里了。我们选择一个站加油，然后继续跑。
3.4 返回值 -1 的时机
很多人写完后会问：什么时候返回 -1？就是当堆已经空了，但 fuel 仍然小于 0 的时候。
例如起点油量为 5，第一个加油站距离起点 10，且这就是唯一一个加油站，那么在主循环处理第一个加油站时，fuel 先减 10 变成 -5，堆为空，while fuel < 0 and heap直接不进入，接下来判断if fuel < 0: return -1，游戏结束。
3.5 复杂度与内存表现
贪心解法的时间复杂度是 O(n log n)，因为每个加油站最多入堆一次、出堆一次，每次堆操作是 O(log n)。空间复杂度是 O(n)，因为最坏情况下所有加油站都会进入堆。
这里特别说一下你标题里提到的“内存”这个热搜词。这道题如果用 O(n²) 的 dp 数组，在极端输入（比如 10000 个站点）下，内存占用会达到 100MB 级别，Python 里这个数值还会更吓人。而贪心法只需要一个堆，内存占用几乎可以忽略不计。这也是为什么 LeetCode 评论区里很多人强调这题“用堆才是正解”。而且在实际面试中，面试官不仅看你能不能 AC，还会追问“你的解法空间复杂度是多少”“能不能优化”，这时候贪心 + 堆的优越性就非常明显了。
4. 实操过程：从暴力到最终的完整实现
4.1 第一版：朴素的“每次找最大”写法
在想到用堆之前，我最初的思路是：每次油不够时，遍历所有已经路过的加油站，找一个油量最大的加。这个思路虽然正确，但每次找最大都要 O(k) 的扫描，整体复杂度会退化到 O(n²)，而且代码写得非常啰嗦。我用一个列表保存经过的站点油量，然后每次 max() 一下，还要手动把用过的站标记掉，最后发现这个版本不仅效率低，而且容易出 bug（比如同一个加油站被加了两次）。
这个失败版本让我意识到，“每次找最大”这个需求，天生就是堆的活儿。贪心的正确实现必须配一个高效的“动态取最大”数据结构，否则思路再好也落不了地。
4.2 第二版：标准堆解法（推荐）
上面 2.2 节给的已经是完整的堆解法。我再用伪代码的形式走一遍流程，方便你对照理解：
- 把终点作为油量为 0 的站点加入列表。
- 初始化 fuel = startFuel、ans = 0、prev = 0，堆为空。
- 遍历每个位置 pos、油量 gas：
- fuel 减去从上一个位置到这里的距离。
- 如果 fuel 小于 0，且堆不为空，循环 pop 堆中最大油量并累加 fuel，ans 加 1。
- 如果 fuel 仍小于 0，说明无法到达当前位置，返回 -1。
- 把当前位置的 gas 入堆。
- 更新 prev = pos。
- 循环结束，返回 ans。
这里我建议你先不要看代码，用纸笔手动模拟一遍这个流程，特别是“先扣油，再判断是否需要加油，最后把当前站油量入堆”这个顺序。顺序很重要，因为你不能在还没到某个站的时候就把它加入堆，否则相当于你可以隔空加油，结果会偏小。
4.3 第三版：边界条件测试
我自己在本地跑测试时，专门构造了这么几个用例来验证正确性：
| 用例场景 | target | startFuel | stations | 预期结果 |
|---|---|---|---|---|
| 起点油够直接到终点 | 10 | 15 | [] | 0 |
| 完全没有加油站且油不够 | 10 | 5 | [] | -1 |
| 第一个站都到不了 | 10 | 3 | [[5, 4]] | -1 |
| 正常多站情况 | 100 | 10 | [[10, 60], [20, 30], [30, 30], [60, 40]] | 2 |
| 加的油量很大，一次补满 | 100 | 50 | [[25, 50], [50, 25]] | 1 |
其中第 4 个用例值得多说一句：目标 100，起始油 10，第一个站距离 10，到站后油为 0，此时油量为 0 但“刚刚好”到达，不算需要加油（因为燃油量不低于 0 就能到站）。到站后把 60 加进堆，继续跑。第二个站在 20 英里处，距离上一个站 10，燃料从 0 减到 -10，此时从堆里 pop 出 60，fuel 变成 50，ans 变 1。继续到 30 英里处，燃料 50-10=40，不需要加油，把 30 入堆。到 60 英里处，燃料 40-30=10，把 40 入堆。最后到终点，燃料 10-40=-30，此时堆里有 30 和 40，pop 40，fuel 变 10，ans 变 2，满足条件，返回 2。但如果另一个用例中是需要在 50 英里处选 25 而不是 40，结果就会不同。
你看，整个过程里我们没有提前规划“在第几个站加油”，而是边走边看，油不够了才在已有选项中选最优，这就是贪心“延迟决策”的精髓。
4.4 实现过程中的注意事项
再补充几个我在实际编程中发现容易踩的坑：
- 站点列表顺序：LeetCode 输入保证 stations 是按位置升序排列的，但如果你自己造数据，一定要先排序，否则整个贪心逻辑全部失效。
- 起始燃料的单位：题目里每加仑油跑 1 英里，所以直接用数字相减即可。如果题目改成每加仑跑 N 英里，那就要把油量乘以 N 再比较，注意换算。
- 堆中油量的重复使用：一个站的油只能加一次。因为我们在油不够的时候才 pop，而且 pop 之后就出堆了，所以天然保证不会重复加。
- 大数溢出问题：C++ 和 Java 里面，如果 target 和油量特别大，累加时可能越界。Python 没有这个问题，但用其他语言时建议用 long 类型。
5. 常见问题与排查技巧实录
5.1 为什么我的贪心解法结果比正确答案大？
这是我把暴力解和贪心解对拍时遇到的一个问题。排查了半天发现，是“判断 fuel < 0 的时机”搞错了。若我在“把当前站油量入堆”之后才判断 fuel 是否为负，就会导致当前位置的油量被提前用于补足到当前位置所需的燃油。
正确的逻辑是：先减距离，如果不够，就只用已经经过的站点油量来补；补完之后，再把当前站油量入堆。这样才符合“你还没到这个站，不能加它的油”的物理规则。
5.2 什么时候返回 0？什么时候返回 -1？
这两个边界很容易混淆。
- 返回 0：起始燃料在完全不加油的情况下，能直接跑到终点。哪怕沿途有几百个站，但只要
startFuel >= target，答案就是 0，不需要遍历站点。 - 返回 -1：无论怎么加油都无法到达终点。如果沿途站点全部用完，燃料仍然不足以到达终点，就说明不可能完成任务。
在代码里，返回 -1 的唯一位置就是 3.4 节说的那个判断。而返回 0 不是显式判断的，因为如果你的初始油就够，那么主循环里永远不会进入 while，ans 一直是 0，遍历完直接返回 0。这也是一种“隐式处理”。
5.3 站点为空时，怎么处理？
如果 stations 为空数组，那么循环不会执行任何一次，直接返回 ans，也就是 0。但这时候要判断 startFuel 是否大于等于 target，如果小于，应该返回 -1。这里就是 3.1 节里“追加终点”技巧的威力所在了：即使站点为空，追加了终点后，循环也会执行一次，统一完成判断。
我在第一次写的时候，单独写了一个if not stations and startFuel < target: return -1来处理空数组，后来改用追加终点的做法后，这段代码就被删掉了。代码的健壮性反而更好。
5.4 堆里存油量还是存“可追加续航”？
这个问题在评论区经常有人问。有人在堆里存的是“当前加油后可以额外跑的距离”，但那是错误的，因为每个站的油量是固定的，不会因为你在哪个位置加而改变。如果你存的是“到达该站时还能跑多远”，那这个值会随着当前油量的变化而变化，存储的值就不稳定了。
所以正确做法是只存每个站的 gas 值。每次 pop 出来就加上，因为这个值是绝对的。
5.5 暴力递归为什么超时？
如果这题你不做任何优化，直接递归枚举“在第 i 个站加不加油”，那就是 2^n 种可能，n 到 100 就彻底超时。所以这道题你必须向面试官传达一个信息：这题可以用 O(n log n) 的贪心解，而不是 O(2^n) 的暴力搜索。这也是 Hard 题“难”的地方——难在你能否想到把选择延后到“不得不选”的时候，而不是难在代码本身有多复杂。
5.6 实际跑 LeetCode 时的内存优化经验
我提交时发现，Python 解法里如果将 stations 原地 append 一个 [target, 0]，不会显著增加内存占用。但如果你用 dp 数组法，且站点数达到 10^5，dp 数组的二维开销会非常恐怖。这也是网上“内存 100”这个热搜词的来源之一——很多人用 dp 做这题时，内存直接爆了，而堆解法稳如老狗。
如果你非得追求极致内存，还可以把stations.append改为stations = stations + [[target, 0]]然后原地迭代，但 Python 里这样会复制列表，反而更费内存。更优的做法是单独用一个变量标记终点判断，但代码会稍微长一点。我个人觉得 append 的方式在可读性和内存上的平衡是最好的。
6. 压轴：一个可以直接抄的通用模板
最后给你一个我用顺手了的模板，不仅仅适用于 871，还适用于所有“资源受限下最少补充次数”的题目。比如 LeetCode 1642（能到达的最远建筑）、630（课程表 III）等，都可以套用同一个思想。
import heapq from typing import List def minRefuelStops(target: int, startFuel: int, stations: List[List[int]]) -> int: # 终点作为最后一个"加油站" stations.append([target, 0]) fuel = startFuel max_heap = [] # 存负数模拟最大堆 ans = 0 prev = 0 for pos, gas in stations: fuel -= pos - prev # 燃料不足时，在已经过的站里选油量最大的补 while fuel < 0 and max_heap: fuel += -heapq.heappop(max_heap) ans += 1 if fuel < 0: return -1 heapq.heappush(max_heap, -gas) prev = pos return ans代码一共就十几行，但里面浓缩了贪心、延迟决策、优先队列、边界统一处理这四个核心点。如果你能把这个模板讲清楚，面试官基本会当场给你这道题打高分。
我个人在实际操作中的体会是：这类“尽量少做某事”的问题，十有八九是贪心 + 某种数据结构；关键不是数据结构本身难写，而是你愿不愿意相信“延迟决策”是安全的。你总会担心“万一前面有个特别大的油站，我没加它却加了这个小的，后面不够了怎么办？”但你要相信，堆这个结构天然会帮你保留最大的选项到现在——你只是推迟选择，而不是放弃选择。
最后再分享一个小技巧：刷 LeetCode 的时候，拿到 Hard 题别急着写代码，先花五分钟想清楚“如果我是司机，我会怎么开”。你会发现，当你把抽象问题还原成现实场景时，贪心策略几乎是直觉性的。这也是为什么我一直推荐面试准备时多用“生活类比法”理解算法题，比死记模板要牢靠得多。
