LeetCode 134这道题，我每次给刷题的新手讲贪心算法，都会把它拎出来当第一个例子。原因很简单：题目背景是加油站，代码最后不过十来行C语言，但能把“为什么这么贪是对的”讲透的人，真不多。很多人看完题解只会背代码，问他“为什么total小于0就一定无解”“为什么cur小于0就把起点跳到i+1”，一下子就卡住了。这篇文章就用最直白的方式，把这道题的贪心思路、数学证明、C语言实现和调试心得一次讲完。
题目本身不复杂：环形公路上有n个加油站，第i个加油站能加gas[i]升油，从第i站开到下一站要消耗cost[i]升油，油箱初始是空的。问能不能找到一个起点，让车可以绕着环形公路走一整圈回到原点。如果能，返回起点下标；不能就返回-1。如果你正好在学C语言，或者刚刷LeetCode不久，这道题就是检验你“会不会用前缀和思维简化环形问题”的试金石。
1. 题目拆解：先搞清楚加油站问题到底在问什么
1.1 把题意翻译成大白话
给你两个等长数组，gas和cost。每个位置i上有两个数字：一个是“你在这个位置可以白拿多少油”，一个是“你从这个位置开到下一个位置必须消耗多少油”。车必须按顺序往前开，开完最后一站之后要绕回第0站，形成闭环。
关键点有两个。第一，油箱一开始是0，所以第一个踩到的加油站可以先加油，加完再出发；第二，每一站你都必须加光当前的gas，因为这站不加白不加，而且题目也没说你可以选择不加。于是从某个起点start出发，到下一站时，你的剩余油量就是之前攒下的油减去开销。如果中途任意一个时刻油量变成负数，这趟就失败。
很多第一次看题的人会在这里绕晕：既然油量是一路攒下来的，那我提前在某个油多的站多加点不就行了？不行，题目没有“提前囤油”这个操作，每站加的油数量固定，唯一能决定的就是从哪一站开始。所以这道题本质上是在一个环上找一个“起点”，使得到任意位置时，前缀和都不小于0。
1.2 暴力解法与它的低效之处
最容易想到的做法就是枚举起点。外层循环从0到n-1试每一个起点，内层循环模拟一整圈。伪逻辑如下。
int canCompleteCircuitBrute(int* gas, int gasSize, int* cost, int costSize) { for (int i = 0; i < gasSize; i++) { int tank = 0; int ok = 1; for (int j = 0; j < gasSize; j++) { int idx = (i + j) % gasSize; tank += gas[idx] - cost[idx]; if (tank < 0) { ok = 0; break; } } if (ok) return i; } return -1; }这个解法逻辑没问题，时间复杂度是O(n²)。n小的时候无所谓，但LeetCode上n可以到10的4次方甚至更大，最坏情况要跑上亿次计算，直接超时。更关键的是，暴力法没有利用一个隐藏信息：如果从i出发，开到某个站k油量不够了，那中间很多站根本不用再试。贪心算法的出发点，就是把这个“不可能区间”直接砍掉。
提示：暴力法的价值在于帮我们验证正确性。我在本地调试贪心算法时，经常会写一个暴力解作为“标准答案”，然后用随机数据对拍。新手学着写对拍，比自己干瞪眼排查快得多。
2. 贪心算法的核心思路与数学证明
2.1 一条关键观察：失败点可以“一刀切”
先定义每个站点的净收益diff[i] = gas[i] - cost[i]。这个值表示：在i站加完油、再开到下一站之后，油箱里的油是变多还是变少。
假设当前候选起点是start，我们从start出发，一路累加diff，第一次出现剩余油量小于0的位置是k，也就是累加到第k个站点时cur < 0。那么结论是：从start到k之间的任何一个加油站，都不可能是可行的起点。
为什么？因为从start开到k之间，cur一直是大于等于0的。这说明start到k之前的所有“前缀剩余”都是正向积累。如果你把起点从start换到中间的某一个点x，本质上等于丢掉从start到x-1这段已经积攒下来的正剩余，而后面要走的路段还是那么长，该消耗的一滴都不会少。起步油量少了，当然只会更早没油。
用式子表达更清楚。设sum(a, b)表示从a到b的diff累加。如果从start出发到k第一次失败，说明sum(start, k-1) >= 0，且sum(start, k) < 0。那么对任意x属于[start+1, k]，有sum(x, k) = sum(start, k) - sum(start, x-1)。因为sum(start, x-1) >= 0，所以sum(x, k) <= sum(start, k) < 0。从x出发到k一样会没油。所以start到k之间的所有点，全部淘汰。
这就是“一刀切”的含义。遇到cur < 0，不用在start和k之间反复试，直接把候选起点跳到k+1，cur清零，继续往后看。
2.2 总油量判断：先看全局可行性
还有一个前置判断：把所有diff加起来得到一个total。如果total < 0，直接返回-1。道理也很直白，一整圈下来，所有站点能加的油总量，还不够一整圈消耗的总量，那不管从哪里出发都注定失败。这就像你出门带多少钱不重要，重要的是这一整趟下来总收入能不能覆盖总支出；收入小于支出，起步点选在哪儿都白搭。
但如果total >= 0，是不是一定有解？答案是肯定有。这一步的严格证明会用到上面的“切割”操作。贪心算法每遇到一个cur < 0，就把这段“负收益区间”整体切掉。到最后如果total >= 0，说明所有被切掉的负区间加在一起，也抵不过最后剩下的那个正区间。而最后剩下的那个起点，因为它在整个环上对应的总油量足够，所以能支撑它走完剩余部分，绕一圈回到自己。
这段逻辑是整道题的灵魂，建议多看几遍。你可能觉得它像“把负数都丢出去，留下正数当起点”，这个直觉没问题。本质上贪心算法在这里做的事情，就是排除所有明显不可能的点，最后剩下的那个候选点，就是唯一可能成功的点。
2.3 为什么可以用一次遍历确定起点
在上面的基础上，实现只需要一个循环。维护两个变量：total记录全局净收益，cur记录从当前候选起点到当前位置的累计净收益。一旦cur < 0，说明当前候选起点失败了，也说明这段区间内所有点都失败了，于是：
- cur归零，重新累计；
- 候选起点start更新为i + 1。
循环结束后，如果total < 0就返回-1，否则返回start。
这里有个特别容易困惑的点：为什么只遍历一圈就敢确定start可行？因为环的长度是固定的，你从start出发，能不能绕一圈回到start，只取决于“从start到数组末尾”这一段以及“从0到start-1”这一段的总收益。而total >= 0已经保证了这两个段加起来是非负的，再加上“失败点切割”保证了start之前不存在能让它失败的阴沟，于是start就是那个答案。
注意：这里有个很多题解不会明说的细节。当total >= 0时，循环结束后的start一定是小于n的，不会出现start等于n的越界情况。原因是：如果最后一个cur < 0触发了start = n，那么被切掉的总共n个站点的累计收益为负，total也就必然为负，与total >= 0矛盾。所以直接返回start是安全的。
3. C语言实现：从思路到完整代码
3.1 最终代码与逐行讲解
LeetCode给的函数签名是int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize)。C语言不像C++有vector，所有数组都靠指针传进来，长度单独给。最精简的贪心实现如下。
int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize) { int total = 0; // 整趟行程的净剩油量 int cur = 0; // 从候选起点累计到当前位置的净剩油量 int start = 0; // 候选起点 for (int i = 0; i < gasSize; i++) { int diff = gas[i] - cost[i]; total += diff; cur += diff; if (cur < 0) { cur = 0; start = i + 1; } } return total < 0 ? -1 : start; }建议先把这段代码抄下来，然后自己在纸上用几个小例子走一遍，比如gas = {1, 2, 3, 4, 5}，cost = {3, 4, 5, 1, 2}，这是题目的示例，答案是3。跟着循环推一下，你会发现cur在i=0、1、2时分别是-2、-4、-6，每次都是负数，start被一路更新到3，到了i=3终于变正。这就是“前面全是坑，跳过完事”的过程。
想要更清晰的话，还可以把代码拆成两次循环，先算total再找起点，便于理解。
int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize) { int total = 0; for (int i = 0; i < gasSize; i++) { total += gas[i] - cost[i]; } if (total < 0) return -1; int cur = 0, start = 0; for (int i = 0; i < gasSize; i++) { cur += gas[i] - cost[i]; if (cur < 0) { start = i + 1; cur = 0; } } return start; }两版效果一致，只是第一版把total判断放循环里一次做完。我推荐第一版，因为面试时手写代码越短越好。但如果你自己学习，第二版更直白：先判断“这趟值不值得走”，再去找起点。
3.2 C语言特有的几个实现细节
一是数组下标问题。暴力解法里才有(i + j) % gasSize这种取模操作，贪心解法完全不需要。因为我们在环形数组上用的是“线性扫描+跳转起点”的思路，取模只在验证答案时才需要。
二是costSize参数。LeetCode上它一定等于gasSize，所以代码里只用gasSize作为循环上限即可。但如果你写单元测试，最好对两个长度都做一次断言，防止有人传错参数。
三是返回值语义。题目要求返回起点下标，不是返回起点的第几个位置。很多C语言新手容易在这里搞混，return i和return i + 1写反。
四是本地测试时的主函数写法。LeetCode只提交函数，不提交main。但你在本地跑，需要自己造main、自己调用函数、自己打印结果。
#include <stdio.h> int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize); int main(void) { int gas[] = {1, 2, 3, 4, 5}; int cost[] = {3, 4, 5, 1, 2}; int start = canCompleteCircuit(gas, 5, cost, 5); printf("start index = %d\n", start); return 0; }然后配合gcc编译运行。这一步对新手特别重要，因为LeetCode网页上的“通过”不会告诉你代码在本地怎么跑，而刷题最终要形成“本地调试+在线提交”的完整闭环。
4. 常见问题与调试实录
4.1 几个高频疑惑的速查表
我在讲这道题的时候，被问过最多的几个问题，整理成一张表。
| 疑惑点 | 解答 |
|---|---|
| 为什么不能找diff最大的点当起点？ | diff最大的点可能前面紧挨着大消耗路段，比如diff序列{5, -10, 6}，最大在0号位，但0号位开不到1号位；真正的起点是2号位。贪心不是“某一点油最多”，而是“某一整段累计收益为正且前面没有拖累”。 |
| total < 0时为什么直接return -1？ | 整圈总收益为负，相当于总收入小于总支出，任何起点都无法让油箱全程非负。 |
| cur < 0为什么要重置成0？ | cur是当前候选起点的“缓存款”。这段累计已经亏了，说明从该起点到当前失败点之间的所有点都不行，必须换一个起点重新攒油。 |
| 为什么返回start前不用对n取模？ | 当total >= 0时，start不可能等于n。具体证明见2.3部分。 |
| 贪心算法能处理“存在多个解”的情况吗？ | 题目保证有解时唯一。即便不唯一，该算法也能返回一个可行解，只是不保证是哪一个。 |
4.2 我用C语言复现时踩过的几个坑
第一个坑：忘记处理total < 0。很多第一次写的人只写cur逻辑，遇到无解用例就输出了一个奇怪的start。调试方法很简单，多准备几组无解数据，比如gas = {2, 3, 4}，cost = {3, 4, 3}，手动算一下total = -1，预期结果是-1。
第二个坑：把start更新成i + 1之后，下一个循环的cur累加起始值搞错。这段代码之所以简洁，是因为它把“更新start”和“清零cur”放在同一个ifs里。如果你把cur = 0写在if外面，或者漏写，结果必然错。我建议新手先按最简版本抄写，跑通后再尝试合并变量。
第三个坑：本地用scanf读数据时，数组越界。很多人喜欢先读一个n，再读n个gas、n个cost。如果你定义了int gas[100005]，循环读入时下标从1开始，而函数里默认从0开始，答案下标就会差1。最好的做法是数据全部按0下标存储，函数也按0下标处理，保持一致。
第四个坑：int溢出。虽然本题数据范围在int内，但做扩展练习时，如果diff累加超过2的31次方，int会溢出成负数，导致total判断出错。应对方法有两种：一是改用long long，二是提前用数学公式避免极端累计。刷题时养成“先看数据范围再选类型”的习惯，面试时你会感谢自己。
第五个坑：不会用printf调试。贪心算法只有几行，很多人觉得没必要打印。实际上你自己写的时候，最容易怀疑“是不是这里重置错了”。我调试时会在循环里打印i、diff、cur、total、start，一眼就能看出失败点在哪里切割。打印代码加个条件判断，只在cur < 0时输出，等逻辑对了再删掉。
5. 从这道题延伸出去的贪心训练
5.1 同类题目的横向对比
LeetCode 134只是贪心算法的一道开胃菜。它和另外几个经典题共享同一个套路：用一个累计量维护“当前候选方案的余额”，一旦余额为负，说明当前方案告吹，直接放弃整段，换下一个候选点。
比如“跳跃游戏”系列。给定一个数组，每个元素表示最多能跳多远，问能不能到终点。贪心做法是维护一个最远可达位置maxReach，遍历时不断更新；如果某个位置i已经超过maxReach，说明跳不到这里，直接返回false。这和加油站“cur < 0就切段”几乎同构。
再比如“买卖股票的最佳时机”，在允许任意次交易且只能持有一股时，贪心策略是把所有上升段的差价相加，每次遇到价格下跌就不做动作。这也是“把正收益段拼接起来，不碰负收益段”的思路。
还有“删数问题”。给定一个数字串和一个删除次数k，要求删掉k个数字后剩下的数字最小。贪心做法是从左到右找逆序对，一旦发现前一个数字大于后一个数字，就删掉前一个，然后从头再找。它同样利用了“发现一个局部破坏结构，立刻执行操作，跳过不可能的最优方案”的核心思想。C语言实现时，这个题比加油站稍微复杂一点，因为操作的是字符数组，需要处理字符串长度和stdio输入输出。
我在搜索引擎的热词里看到很多人同时搜“删数问题贪心算法”和“翁恺C语言练习题”，说明这条学习路径非常常见：先跟着翁恺老师的课学C语言基础，然后开始刷算法题。二刷加油站之后，再把上面几个题连起来做，你就能明显感觉到，所谓贪心算法并不是“瞎猜一个策略”，而是一套“可证明的局部最优推导”。
5.2 给不同基础读者的练习建议
如果你刚学C语言，建议先不要急着看题解。第一步，把暴力解法的代码自己写出来，跑通示例。第二步，在纸上画出diff数组，用“前缀和”的方式人肉模拟一遍贪心过程。第三步，再对比题解代码，这时候你会突然看懂为什么cur和total各司其职。第四步，写一个本地测试主函数，把函数封装好，以后刷其他题也能复用这套“本地编译+测试”的环境。
如果你已经有算法基础，只是想把贪心吃透，我建议你思考三个变体。第一个变体：如果每个站点的gas和cost都是浮点数，代码还能用吗？第二个变体：如果油箱有容量上限，每个站点加油后最多装M升，这道题还能用贪心吗？第三个变体：如果题目不保证解唯一，让你输出所有可行起点，怎么改造？这三个问题想清楚，你的收获会比单纯背代码大得多。
我个人在实际教学里还有一个习惯：让学生把这道题用三种语言各写一遍，C语言版本、Python版本和Java版本。C语言版本逼你理解数组和指针，Python版本逼你丢掉内存管理的包袱，Java版本逼你注意包装类型和int范围。写完之后你会发现，贪心算法的核心根本不在于语言怎么写，而在于你心里是否真有那条“失败点切割”的线。
提示：最后分享一个我在面试中亲测好用的答题套路。先花30秒说清暴力解O(n²)为什么不优，再抛出关键观察“第一次失败点之前的点全都不可能是答案”，最后写出O(n)代码并解释total >= 0保证了答案存在。这套话术能让面试官快速确认你真的理解贪心，而不是背模板。
这道题刷完，记得把题目收藏起来，过两周再独立写一遍。什么时候你能在5分钟内默写出正确代码，并且能顶住追问把证明说清楚，LeetCode 134才算真正过了。后续遇到“环形数组”“前缀和”“贪心失效怎么补救”这类话题时，这道题就是你脑子里第一个跳出来的参照样本。
