LeetCode 134这道题我每次给刷题的新手讲贪心算法都会把它拎出来当第一个例子。原因很简单题目背景是加油站代码最后不过十来行C语言但能把“为什么这么贪是对的”讲透的人真不多。很多人看完题解只会背代码问他“为什么total小于0就一定无解”“为什么cur小于0就把起点跳到i1”一下子就卡住了。这篇文章就用最直白的方式把这道题的贪心思路、数学证明、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属于[start1, 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之间反复试直接把候选起点跳到k1cur清零继续往后看。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在i0、1、2时分别是-2、-4、-6每次都是负数start被一路更新到3到了i3终于变正。这就是“前面全是坑跳过完事”的过程。想要更清晰的话还可以把代码拆成两次循环先算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为什么要重置成0cur是当前候选起点的“缓存款”。这段累计已经亏了说明从该起点到当前失败点之间的所有点都不行必须换一个起点重新攒油。为什么返回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才算真正过了。后续遇到“环形数组”“前缀和”“贪心失效怎么补救”这类话题时这道题就是你脑子里第一个跳出来的参照样本。