1. 题目拆解与整体思路
1.1 先把这个“最低加油次数”问题翻译成人话
LeetCode 871题，Minimum Number of Refueling Stops，属于典型的“决策类”困难题。题目描述其实不长：你开一辆车从起点出发，初始油量是 startFuel，终点距离是 target 英里，路上有若干个加油站 stations，每个加油站有一个位置和可以提供多少油。车每行驶1英里消耗1加仑油，问你最少加几次油能到终点，如果到不了就返回 -1。
我第一次读这题时，脑子里冒出来的念头是“这不就是个普通的最短路吗”，后来认真捋了一遍才发现不是那么回事。问题的核心难点不在于“能不能到”，而在于“怎么选”——路上的加油站每个都可以加也可以不加，你当前油量不同、位置不同、后续站点的分布不同，都会影响最优决策。这种每个节点多个选择的题，第一反应往往就是动态规划。
但真正把它当DP做，你会发现状态定义非常别扭。更漂亮的解法其实是贪心 + 优先队列（最大堆），时间复杂度能从 O(N^2) 降到 O(N log N)。这也是这题能进“困难”的原因：不是代码难写，而是思维拐弯的幅度比较大。本文结合我自己的刷题过程和近期在内存方面的思考，把这题的思路、实现、边界和延伸全部拆开讲一遍。
1.2 把“加油”这个动作重新定义一个含义
在做任何算法之前，我们先做一步关键的问题建模。汽车从起点出发，当前油量是 curFuel，行驶到下一个加油站的距离是 dist，那么能不能抵达这个加油站，本质是判断 curFuel >= dist。一旦能跑到某个加油站，摆在面前的就是“加不加它的油”的问题。
这里有个非常重要的转化：加不加油，不是在你到达加油站的那一刻决定的，而是在“最需要的时候”去补之前的决策。什么叫做最需要的时候？就是当你发现剩余油量不足以开到下一个加油站时，你会被迫从已经路过的、但当时没加的加油站里，选择一个油量最大的补上。
这就把问题从“预先规划”转化成了“事后补救”。你每到一个加油站，什么都不用急着决定，只是把这个站能提供的油量先寄存起来，等到油不够了，再从寄存区里取出最大的那个补上。如果补完还是不够，再继续取下一个。这种思想在算法题里有专门的名字，叫“贪心 + 延迟决策”，这类问题的常见场景是：活动安排、最大收益、跳跃游戏。
1.3 为什么动态规划不是首选？一个 O(N^2) 方案的局限性
聊一下为什么这题虽然可以用DP，但DP不是最佳方案。
定义 dp[i] 表示加 i 次油能到达的最远距离，这个状态其实比“到第几个加油站”要直观一些。状态转移是：遍历每个加油站 station[j]，如果 dp[i] >= station[j].position，就说明加完 i 次油后能到达这个加油站，此时可以更新 dp[i+1] = max(dp[i+1], dp[i] + station[j].fuel)。
这个思路能 AC，但它的时间复杂度是 O(N^2)，因为你要在每个“加油次数档位”上遍历所有的加油站。当 N 达到 500、1000 时还勉强能跑，但如果是 10^5 级别的数据量，O(N^2) 就彻底没戏了。LeetCode上这题的 N 范围是 1 到 500 左右，所以DP也能过，但面试时如果你只给出 DP 解法，面试官大概率会追问一句：能不能做到 O(N log N)？
而贪心 + 优先队列，恰恰就是把“遍历所有加油站来更新 dp”这个耗时动作，优化成了“每次只取最大元素”的 O(log N) 操作。从内存角度看，O(N^2) 的 DP 需要维护一个长度为 N+1 的一维数组，看似只有 O(N) 空间，但如果把它优化到“只需要一个最大堆”，辅助空间会少很多。尤其当你处理的是超大数据集时，这种空间上的优势会被放大。这也是我刷题时格外关注“内存占用”的原因——刷题不只是看时间复杂度和 AC 行数，空间复杂度同样直接影响实际工程中的可行性。
2. 贪心 + 最大堆实现方案
2.1 算法流程：从“边开边后悔”到“最优补油”
贪心 + 堆的解法，完整流程分四步。
第一步，当前油量 curFuel 初始化为 startFuel，加一个变量 ans 记录加油次数，准备一个最大堆 maxHeap，专门用来存放“已经路过但还没有加的加油站油量”。
第二步，把 stations 数组的末尾逻辑上再延长一个虚拟站点，位置是 target，油量为 0。为什么要这样？因为终点的行为模式和加油站很相似：你判断“能不能到达”的标准是一样的，都需要用当前油量和距离比较。为了让循环逻辑统一，最省事的方式就是直接在遍历时把 target 当作一个特殊站点处理，而不需要真的修改数组。
第三步，遍历每一个站点（包括虚拟的终点站）。每次先计算当前位置到该站点的距离 dist = stations[i][0] - curPosition，然后用当前油量扣除这个距离：curFuel -= dist。如果 curFuel 变为负数，说明中途没油了，此时循环从最大堆里弹出油量最大的站点补给，curFuel += 弹出的油量，ans++，然后再检查一次 curFuel 是否足够。如果堆弹空了还不够，直接返回 -1。
第四步，到达站点后，把这个站点的油量（如果是真实加油站）塞入最大堆，更新当前位置为站点位置，继续下一轮。
这个过程最反直觉的地方在于：你并不是“到了加油站就加油”，而是“没油了才回头加”。但回头加的时候，你能从所有经过的站点里选油量最大的那个，所以一定不会错过最优解。
2.2 完整代码与逐行解读
我贴一份 Python 实现，这是 LeetCode 上最直接也最容易理解的写法：
import heapq class Solution: def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int: max_heap = [] cur_fuel = startFuel ans = 0 pre_position = 0 for position, fuel in stations: cur_fuel -= position - pre_position while cur_fuel < 0 and max_heap: cur_fuel += -heapq.heappop(max_heap) ans += 1 if cur_fuel < 0: return -1 heapq.heappush(max_heap, -fuel) pre_position = position # 最后判断能否到达 target cur_fuel -= target - pre_position while cur_fuel < 0 and max_heap: cur_fuel += -heapq.heappop(max_heap) ans += 1 if cur_fuel < 0: return -1 return ans为什么堆里存的是负数？因为 Python 的 heapq 默认是最小堆，我们要让最大元素先弹出，就得取负存入。这是一个非常高频的 Python 技巧，几乎每道用到堆的题都会踩到。
主循环的逻辑是：遍历真实加油站，遇到一个站点，先看看从上一个位置到这里消耗了多少油，如果油不够就不断从堆里“取最大油量”补上。补完后如果能到达当前站点，就把这个站点的油量压入堆。最后，把 target 当作虚拟终点站重复同样的逻辑。
我特意把“最后判断 target”独立出来，这样代码清晰一些。也有人喜欢在 stations 后面追加[target, 0]，两种写法各有利弊：追加之后循环体统一，代码更短；但追加操作会多一次数组拷贝，如果站在内存优化的角度看，独立写后面的判断逻辑，可以完全避免创建新数组。
2.3 复杂度分析与计算过程
时间复杂度上，每个加油站最多被压入堆一次、弹出堆一次。压入和弹出的复杂度都是 O(log N)，所以整体时间复杂度是 O(N log N)。这个下界能不能再优化？理论上如果你给所有站按油量排序，又要同时按位置顺序访问，这两者是冲突的，所以 O(N log N) 已经是很理想的结果。
空间复杂度方面，最大堆中最多会同时存 O(N) 个元素，每个元素是一个油量整数。如果你在 Python 中直接heapq.heappush(max_heap, -fuel)，除了堆本身之外，代码几乎没有额外的大块内存开销——这里的辅助空间只有堆里的 N 个整数和两三个游标变量。对比一下 DP 方案需要维护长度为 N+1 的 dp 表，虽然同为 O(N) 空间，实际占用大概是堆方案的好几倍，因为 dp 数组的每个元素都是 Python 的 int 对象，内存并不紧凑。
如果你非常在意内存，还可以做一个小优化：不需要pre_position游标，直接用当前油量递减的方式cur_fuel -= station[0] - last_position，这个last_position其实可以替换成“到上一个站时已经行驶的总距离”。但如果用总距离，需要多一个变量记录行驶里程，反而多占一个寄存器。这种级别的优化在 LeetCode 上意义不大，但对“内存 100”这个主题来说，至少说明一个问题：空间复杂度不是只看 Markdown 里写的 O(1)、O(N)，还要看实际语言实现中每个对象的真实大小。Python 的 int 是 28 字节起步的任意精度整数，100 万个 int 就是一亿字节级别的内存。真要做大规模数据处理，换 C++ 或者 Go 的内存表现会好很多。
2.4 证明贪心正确性：为什么“事后补油”不会漏掉最优解
很多初学者不敢用贪心，就是怕证明不严密。这题我用反证法拆一下，帮助你把“为什么对”记扎实。
假设存在一个最优解，它的加油次数是 K（K 是最小值）。在这个最优解中，假设在某一段路程上，你在加油站 A 加了油，而在我们的贪心方案中，我们在这个加油站并没有现场加油，而是路过了它，后来在加油站 B 才加油。由于 B 是在 A 之后出现的，而我们是把 A 的油“留到后面用”，说明“推迟加油”这个动作在油量上不会造成丢失——我们只是把一个本来应该早加的油延后到了需要的时候加。
需要证明的是：在“没油了，必须补充”的时刻，从已路过未加油的加油站中选择油量最大的那个，一定不会比选一个较小的加油站更差。这个可以用交换论证：假设在某次补给时，最优解选择了油量较小的 x，而实际存在一个已路过的油量较大的 y 还没被使用，那么我们在这次补给选择 y，之后依然可以在需要时使用 x，把两者顺序交换，总油量在任意时刻都不会减少。因为 y 的油量更大，交换后“当前油量更低”的情况只会更晚出现，所以绝不会让后续状态变差。
这个证明虽然简短，但它是整个贪心策略的基石。面试时能把这段讲清楚，比闷头写代码要加分得多。
3. 关键细节、边界条件与极致内存优化
3.1 最容易翻车的四个边界场景
边界条件一：stations 为空。如果起点油量 startFuel 本身就能直接开到 target，那答案直接返回 0；如果不够，返回 -1。代码里主循环直接跳过，最后 target 判断会处理，逻辑上不用单独 if，但建议你在测试时显式覆盖一下。
边界条件二：target 小于等于 startFuel。这种情况其实连循环都不用进，答案 0。这在题目给出的测试用例里常见，但很多人在写的时候忽略了这个短路判断，导致多跑一次循环，轻微浪费，不影响正确性。
边界条件三：恰好卡在加油站位置。当你到达某个加油站时，curFuel 刚好变成 0，此时能不能加油？其实是能加的。题目没说油量为 0 就不能进加油站，所以代码中if cur_fuel < 0的判断用的是严格小于，等于是允许“刚好用完”。这个是高频易错点，有人误写成了if cur_fuel <= 0，导致恰好在加油站的位置抛异常或者误判无法到达。
边界条件四：终点 target 前面没有加油站，且油量不够。这种场景下堆永远是空的，所以while cur_fuel < 0 and max_heap循环直接跳过，随后if cur_fuel < 0触发，返回 -1。这部分逻辑很顺，但我见过有人把堆判断和返回 -1 的顺序写反，导致堆空时抛出异常而不是返回 -1。
另外还有一个细节：stations 数组本身是按键 position 升序排好的，LeetCode 的题目保证有序，但你写在工程代码里要主动确认这一点。如果输入没有排序，贪心算法直接失效。常规做法是在函数入口加一句stations.sort(key=lambda x: x[0])，一行代码避免整场事故。
3.2 空间复杂度从 O(N) 到实际内存最小化
大家总说堆占的空间是 O(N)，但这并不代表你的空间优化空间已经封顶了。尤其题目标题里带了一个“内存100”，我就把这一节讲的细一点。
第一，如果你使用 Python 默认的全局命名空间，所有变量都存在模块级，每次函数调用都会多几次全局查找。把它改成局部变量就能让 CPython 的 LOAD_FAST 指令替代 LOAD_GLOBAL，这个优化对刷题没什么用，但对内存常驻服务有意义。
第二，stations 数组里的元素是长度为 2 的 List，每个元素都是独立的 Python 对象。如果你从文件里读取这些数据，其实可以不用一次性全部加载，而是流式处理：每来一个站点，就判断油量并压入堆，处理完就丢弃。这样可以避免同时保留整个二维数组和堆这两份数据。LeetCode 的测试用例已经把所有站点给你了，所以你没法省这份，但工程实践里这是一个真实的优化点。当站点数量达到几百万级时，流式读取配合 MaxHeap，内存占用能降低一个数量级。
第三，如果你真要用 Python 处理大规模数据，可以考虑把 stations 改成两个独立的数组，一个存位置一个存油量，或者直接用array('i')这种紧凑的原生数组，而不是 List。一个 Python int 对象占 28 字节，而 C 语言的 int 只占 4 字节，光是数据存储就能省 85%。当然，这个方案在 LeetCode 的题解里显得有点“杀鸡用牛刀”，但如果在内存受限的嵌入式环境或者超大数据集场景里，这就是关键优化了。
第四，有一个隐藏得很深的坑：Python 的负整数对象是单独分配内存的。你在heapq.heappush(max_heap, -fuel)时，每个-fuel都会产生一个新的 int 对象。如果你后续又要弹出并做取反运算-heapq.heappop(max_heap)，还会有第二次对象分配。这意味着频繁的压堆弹堆操作会触发大量内存分配和 GC 活动。遇到超大数据量或内存受限时，可以改用 C++ 的priority_queue或者手动维护一个大的预分配数组来做堆，内存效率和速度都会明显提升。
3.3 堆选择的最大坑：千万别用最小堆
写这道题时，我看到过不少人第一次提交用成了最小堆。他们的逻辑是“每次补油时选最小的油量，把大的留到后面”，然后算法跑出来结果不对。原因很简单：当你已经缺油的时候，你需要的不是一个“保守”的加油方案，而是一个“最大程度续命”的方案。你当前的任务是活下去到下一个加油站，而不是精打细算把大油量留到未来——因为如果现在都活不下去，未来就不存在了。
想一想，这其实和生活中的“危机管理”很像：人在缺钱的时候，第一反应不应该是“省着花”，而应该是“先找最大的收入来源顶上去”。算法只是在数据层面复现了这种直觉。
除了最大堆和最小堆的混淆，还有人会把堆初始化为“存站点油量的数组”，然后每次缺油时重新对该数组排序取最大值。这种“手动堆”虽然也能得到正确答案，但每次排序是 O(M log M)，而且还要复制数组，时间、空间都变差了。既然标准库提供了堆结构，就直接用，不要重复造轮子。
4. 相似题模式与面试延伸
4.1 一维决策题的通用模式：贪心 + 延迟决策
LeetCode 里有一大类题，解法核心和 871 完全同构。最典型的是 55 题“跳跃游戏”和 45 题“跳跃游戏 II”。跳跃游戏问你能不能跳到终点，跳跃游戏 II 问你最少跳几次——它们同样是在每个位置有一个“可跳距离”，你需要决定什么时候跳、跳多远，才能用最小步数到达终点。
如果把 45 题的思路写出来，你会发现也是“贪心 + 扫描”：当前步的可达范围内，选出下一步能覆盖最远的位置，然后把 step 加一。这和 871 题“没油的时候从已经路过的加油站里取最大油量”在抽象层面是一致的：都是局部最优选择，都没有回头看的全局后悔。
再比如“区间调度问题”、“会议室 II”，它们的共性都是“按某个维度排序，然后用堆维护另一个维度的最优”。这给你一个启示：刷题时不要孤立地记题解，而是建立模式库。看到“最小数量使得可达”，立刻应该联想到这么几条可选路径：DP、贪心 + 堆、BFS。871 题就是一个非常好的模式切片，因为它既包含 DP 的解法，又包含贪心 + 堆的加速，两种方案对比起来特别清晰。
4.2 变体题的灵魂拷问：如果把油箱容量限制加进来
我在做这道题的时候，自己脑补了一个变体：如果汽车有一个最大油箱容量 limit，每次加油不能超过这个容量，那贪心方案还行不行？
答案是不行了。因为“把大油量留到后面加”这个策略，会受到容量上限的约束——你可能路过一个大油量的加油站，但因为油箱满了，只能加一点点，剩下的油量白白浪费。此时问题变成一个带约束的决策问题，贪心的局部最优不成立，得改用 DP 甚至更复杂的带权匹配模型。
这个变体提醒我们：算法题的能力边界，往往不是把一道题 AC，而是能明确说出某个方案在什么条件下失效。面试官问变体题，考察的核心就是你有没有理解原题解法成立的假设。
4.3 面试追问：证明、状态定义、复杂度缺一不可
面试中如果被问到 871 题，我建议你按顺序说三件事。
第一件事是状态定义。先说明这题可以用 DP，定义 dp[i] 为“加油 i 次能到达的最远距离”，并解释为什么要这样定义而不是“到达第 i 个加油站的最小加油次数”——因为后者会丢失“能走多远”这个连续量信息。
第二件事是贪心优化。说明当 N 很大时 O(N^2) 不可接受，你把决策延迟到“缺油”那一瞬间用堆来做，时间复杂度降为 O(N log N)。
第三件事是证明。讲清楚为什么选最大油量是正确的，用交换论证。这一条很多人会卡壳，因为平时刷题只保证 AC，不写证明。我的经验是：LeetCode 困难题几乎都藏着值得深挖的证明，花时间推一遍，比多刷十道简单题都值。
除了这些，面试官还喜欢追问“如果 stations 不是有序的呢？”答案是先排序，排序后原算法不变，这又引入一个 O(N log N) 的排序，总复杂度仍然是 O(N log N)。另外一个追问是“如果允许提前知道所有站点，是否可以做更优？”答案是可以，但状态空间更复杂，不划算。
5. 常见问题与排查技巧实录
5.1 五个高频报错场景对照
我自己刷这题以及帮同事 review 代码时，发现常见的错误类型相当集中，整理成一张速查表：
| 症状 | 根因 | 修复方式 |
|---|---|---|
| 返回 -1 但实际有解 | 到达加油站时 curFuel 为 0，被<=误判为无法到达 | 改为curFuel < 0 |
| 死循环 | 油量补了之后没有更新当前位置，导致重复消耗同一段距离 | 每次循环确保position或pre_position前移 |
| 结果偏小 | 使用了最小堆，每次取最小油量 | 改为最大堆（Python 取负） |
| 结果偏大 | 到了加油站立刻加油，没有延迟决策 | 改为“没油时再弹堆补给” |
| 内存超限 | 反复复制 stations 数组或创建大量临时 List | 使用索引遍历，不要在循环内部stations[i:i+1]切片 |
这里我要特别提一下“结果偏小”和“结果偏大”的区别。如果你用的是最小堆，你会在每次缺油时加最小油量，可能一次加不够还要弹更多次，所以答案是偏大的；如果你到了加油站就立刻加油，可能会过早耗尽一些大油量，导致后续需要更多次，答案也是偏大的。只有“先攒着，缺了再取最大”才是答案偏小（不过因为没有更优解，所以它不会真的比最优解小）。
5.2 构造最小用例排错的实操方法
排查算法问题的标准动作：找最小反例。871 题我建议你准备这么几个固定用例来测试。
target=100, startFuel=50, stations=[]：预期 -1，因为没有油也到不了。target=100, startFuel=100, stations=[[50, 10]]：预期 0，初始油量足够，不需要进加油站。target=100, startFuel=50, stations=[[10, 100], [90, 20]]：预期 1，因为有在 10 英里处加 100 加仑足够直接到终点。target=100, startFuel=50, stations=[[60, 40], [90, 10]]：预期 2，你必须在两个站都加油才行。
把这几组用例跑通，核心逻辑基本就稳了。然后再测一个压力数据，比如 N=500 的随机数据，对比 DP 解法和贪心解法的结果是否一致。一旦差异出现，锁定差异发生的前后几个加油站，几乎立马就能定位错误。
5.3 用输出调试还原贪心过程
有一个调试技巧，特别适合理解这类题：在 while 循环内部打印每个加油站的位置、当前油量、堆里的元素、加油次数。我贴一个调试片段：
for position, fuel in stations: cur_fuel -= position - pre_position print(f"到达站点 {position}, 当前油量 {cur_fuel}, 堆内元素 {max_heap}") while cur_fuel < 0 and max_heap: gained = -heapq.heappop(max_heap) cur_fuel += gained ans += 1 print(f" 缺油，从堆中补油 {gained}, 当前油量 {cur_fuel}, 加油次数 {ans}") if cur_fuel < 0: return -1 heapq.heappush(max_heap, -fuel) pre_position = position这样跑一次，你能直观看到“油量什么时候跌破零”“堆里选出了谁”“加油次数怎么累加”三个关键过程。我建议每个对贪心不舒服的人都在本地跑一跑这个打印版，跑完会有种“从恍然大悟到彻底记住”的感觉。
5.4 与“内存 100”相关的两个真实工程提醒
最后聊两句工程上的内存话题。这类贪心 + 堆的题目，在算法比赛和 LeetCode 里算是轻量级，但在真实数据流水线里，等价逻辑可能会被用于“资源调度”“缓存规划”。此时内存占用就是实打实的成本问题。
第一个提醒：堆的大小不是无限增长的。虽然最坏情况 O(N)，但在真实场景里，你可以在“弹堆”之后顺手清理已失效的站点引用，避免堆里堆积大量无用的历史数据。LeetCode 的 stations 是线性数组，不需要清理；但如果你的加油站对象是动态生成的实体，不及时清理会导致内存泄漏，时间一长 GC 压力剧增。
第二个提醒：如果数据量上百万，建议用数组预分配方式实现二叉堆，而不是依赖语言标准库的动态扩容堆。标准库堆在扩容时可能临时占用翻倍内存，达到内存峰值的瞬间，恰好就是你“内存 100%”的时刻。用预分配数组，内存从申请开始就固定，不会出现峰值暴涨。这是我踩过真实生产环境里的坑——数据量一上来，GC 停顿能把吞吐拖垮。
结尾：一点真切的刷题体会
这题我前前后后刷了三遍。第一次用 DP 过了，觉得自己挺厉害；第二次整理题解时写贪心 + 堆，被“先路过再后悔”的思维方式狠狠震了一下；第三次是带一个学弟 review 代码，他问了我一句“为什么不在到站时加油”，我发现自己第一次讲不清楚这个“为什么”。从那以后我养成了个习惯：做困难的贪心题，一定要能用大白话把正确性讲给完全不懂算法的人听。
871 题让我最有收获的，不是那个 AC 的按钮，而是它把“资源管理”的本质浓缩成了一个简单的模型：你永远不知道未来哪个资源更稀缺，所以你先收集所有的可能性，等危机出现的那一刻，再调用最强的手段。这和做工程、做预算、做规划其实是同一个道理。
如果你正在刷这题，我也建议你按“DP 到贪心、贪心到证明、证明到变体”的顺序走一遍。别急着看题解，先用自己的笨办法跑通，再回头看最优解，那个“原来还能这样”的落差感，才是刷题最值钱的部分。
