前两天刷题群里有人贴了 LeetCode 134 的代码说他模拟跑了一遍样例能过一提交直接超时。我一看就知道问题出在哪这题用暴力模拟去验证每个起点复杂度直接 O(n^2)数据量一大必然吃瘪。LeetCode 134 加油站这道题表面是个环形数组的模拟问题实际上是学习贪心算法最好的入门案例之一而且用 C 语言写起来非常干净核心代码不到 20 行。今天我就把这个题的贪心思路、正确性证明、完整 C 语言实现和一些容易踩的坑从头到尾讲清楚适合正在刷题准备面试的、刚学完 C 语言想练习算法的朋友也适合那些感觉自己懂贪心但总说不清为什么的人。1. 题目到底在问什么别被环形场景带偏1.1 先把题目翻译成人话题目给了两个长度相同的数组gas[i] 表示你在第 i 个加油站能加的油量cost[i] 表示从第 i 个加油站开到第 i1 个加油站要消耗的油量。车一开始油箱是空的你可以从任意一个加油站出发问能不能绕环形路线一圈回到起点能的话返回那个起点的下标不能就返回 -1。有个细节很多人第一次做时会忽略你的车在某个时刻油量可以为负数吗不行。只要当前剩余油量小于 0就说明你从所选起点根本开不到当前这个位置这条路直接淘汰。所以整道题本质上是在做一件事从 n 个候选起点里找到一个起点使得从它出发绕一圈的过程中任何时刻累计剩余油量都不小于 0。这里可以打个比方你带了一笔钱出门逛街经过每个店你都会有点收入gas但走到下一家店要花钱cost你兜里的钱任何时候都不能是负的否则这段路就走不下去。问题就是选哪个店作为出发起点能让你把整条商业街逛完一圈还不破产。1.2 暴力模拟为什么很自然也很贵很多人的第一反应是那我从 0 号站开始试不行就换 1 号再不行换 2 号每个起点都模拟完整走一圈总有一个能行。这个思路完全正确没有任何逻辑错误问题只有一个字慢。每个起点模拟一圈需要遍历 n 个加油站一共 n 个候选起点所以总复杂度是 O(n^2)。假设 n 10^5那就是 10^10 次加减运算即使你的电脑每秒能跑 10^8 次操作理论上也要 100 秒。LeetCode 的判题系统当然不可能给你这么多时间超时几乎是必然的。如果你用 C 语言写暴力版本代码可能是这个轮廓int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize) { for (int start 0; start gasSize; start) { int cur 0; int ok 1; for (int step 0; step gasSize; step) { int idx (start step) % gasSize; cur gas[idx] - cost[idx]; if (cur 0) { ok 0; break; } } if (ok) return start; } return -1; }逻辑没毛病但每次失败都要从头再来前面走过的路全部白走。这就是为什么我们需要贪心能不能在一次遍历里把明显不可能的起点直接淘汰掉只保留一个候选起点2. 贪心思维的两次关键跳跃2.1 第一跳总油量小于总消耗直接判死刑这一步是最简单也最容易被人忽略的。你想绕一整圈车的油箱最终回到起点时总剩余油量必须不小于 0。整个环形路线里你一共能获得的油是 sum(gas)一共要消耗的油是 sum(cost)。如果 sum(gas) sum(cost)那么没有任何起点能完成一圈直接返回 -1。为什么因为绕一圈是闭合的这一圈的净消耗如果大于总收入不管从哪出发起点处的初始油量都是 0你不可能凭空变出油来。这就好比你想跑完一个马拉松但沿途补给站提供的总能量比全程消耗的能量还少那你不管从哪个补给站起跑注定中途要倒下。用代码表示就是在遍历过程中累加一个 totaltotal gas[i] - cost[i];最后看 total 是否大于等于 0。这个判断不是可选项它是整个贪心算法正确性的地基之一。没有了它就算后面选出了一个候选起点也无法保证它真的能完整绕一圈。2.2 第二跳累计油量跌破 0果断抛弃整个区间这是整道题最核心的贪心思想也是很多人最不理解的地方。我们定义一个变量 cur表示从当前候选起点到当前位置 i 的剩余油量。每次遍历到一个加油站 i执行cur gas[i] - cost[i];如果 cur 一直大于等于 0说明当前候选起点到目前为止都是可行的。但是如果 cur 在某个位置 i 处小于 0 了说明什么说明从当前候选起点 start 出发你连 i 都开不到更别提绕一圈了。此时正确的做法是把候选起点直接改为 i 1并把 cur 重新清零。很多人到这里会问为什么是 i 1为什么不是 start 1为什么不可能是 start 和 i 之间的某个点这个问题的答案就是贪心算法的精髓。我们可以这样想从 start 出发走到 i油量才跌破 0说明在到达 i 之前你在 start 到 i 之间的任何位置手里的油量都是大于等于 0 的。也就是说你在 start 处出发时带了一个正的起始资产。现在如果你从 start 和 i 之间的某个中间点 k 出发你失去了从 start 开到 k 这一段积累下来的正油量那么在到达 i 的时候你的油量只会比从 start 出发时更少更不可能是正的。换个更直白的说法如果你从 A 点出发能走到 D 点但身上剩的钱不够了那从 A 和 D 之间的 B 点出发到 D 时你身上的钱只会更少因为你少了从 A 到 B 这一路攒下来的积蓄。所以start 到 i 之间的所有点都不可能成为合法起点直接全部扔掉下一个唯一可能的起点是 i 1。这也就是贪心里的贪字每一步都在用当前信息做出局部最优决策但这个局部最优决策恰好能保证全局结果正确因为它把一整段不可能的解空间一次性裁掉了。3. C 语言实现20 行解决附完整测试代码3.1 核心函数代码把上面的思路翻译成 C 语言核心函数就是这个样子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) { start i 1; // 之前的区间全部淘汰 cur 0; } } return total 0 ? start : -1; }代码量确实不到 20 行而且只用了一个 for 循环空间上连额外的数组都没有开时间复杂度 O(n)空间复杂度 O(1)。3.2 逐行拆解为什么这三个变量就够用先看 total。它从头到尾只做累加从不因 cur 清零而重置。它承担的是全局面板的角色记录整个环形路线总的净收益。最后 total 如果大于等于 0说明油总量够用如果小于 0直接返回 -1。再看 cur 和 start。这两个变量是配合工作的。cur 记录的是从当前 start 出发到当前位置 i 这半段路的累计剩余油量。一旦 cur 小于 0说明这个 start 已经被证明不可行而且 start 到 i 之间的所有点也全部不可行于是 start 跳到 i 1cur 归零重新开始累加。有人会问start 会不会跳到数组越界的位置比如 i 是最后一个元素时start 变成 gasSize。这种情况确实可能出现但你会发现此时 total 一定小于 0。因为如果 total 大于等于 0那么最后一个元素处的 cur 不会为负。所以代码里 start 越界的时候total 必然触发 -1 分支start 的值根本不会被返回。这也是为什么不需要额外做取模处理。最后返回 start 之前为什么不用再模拟验证一遍这就要说到贪心正确性的保证了如果 total 0那么从 start 出发cur 在整个遍历过程中始终没有掉到 0 以下有掉的情况早就跳转 start 了而后面那段路之所以能走完是因为总收益能覆盖前面那段的亏损。这个结论的严格证明放在第 4 节讲。3.3 配套测试代码本地跑起来才有手感LeetCode 上只要提交函数即可但本地调试时需要自己写 main 函数。给一个可以直接编译运行的完整示例#include stdio.h int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize); int main(void) { int gas1[] {1, 2, 3, 4, 5}; int cost1[] {3, 4, 5, 1, 2}; int gasSize1 sizeof(gas1) / sizeof(gas1[0]); int costSize1 sizeof(cost1) / sizeof(cost1[0]); int result1 canCompleteCircuit(gas1, gasSize1, cost1, costSize1); printf(Test 1: %d\n, result1); // 预期输出 3 int gas2[] {2, 3, 4}; int cost2[] {3, 4, 3}; int gasSize2 sizeof(gas2) / sizeof(gas2[0]); int costSize2 sizeof(cost2) / sizeof(cost2[0]); int result2 canCompleteCircuit(gas2, gasSize2, cost2, costSize2); printf(Test 2: %d\n, result2); // 预期输出 -1 return 0; }第一个用例很经典从下标 3 的加油站出发加 4 升油消耗 1 升到 4 还剩 3 升再加 5 消耗 2到 0 还剩 6再加 1 消耗 3到 1 还剩 4再加 2 消耗 4到 2 还剩 2最后加 3 消耗 5回到 3 时刚好剩下 0。一圈走完没断油所以返回 3。如果不想硬编码数组也可以自己写 scanf 读取输入。比如先读 n再读 n 个 gas再读 n 个 cost在本地验证自己的解法。LeetCode 的 C 语言题目只需要实现函数但面试时经常要求手写完整程序所以这个 main 函数值得保存备用。3.4 三个新手常踩的坑第一个坑忘记 total 的判断。有些人写完循环直接 return start结果某些数据下 start 指向一个根本跑不完的起点。必须记住total 0 是返回 start 的前提。第二个坑把 cur 0 写成 diff 0。diff 只是单站净油量单站为负不代表从起点出发到这里会断油因为前面可能攒了很多油。贪心的关键在于累积量 cur而不是单站量 diff。例如 gas [5, 1, 1], cost [2, 3, 1]下标 1 的 diff -2但下标 0 的富余足够撑过去。第三个坑用取模强行写环形遍历代码变复杂。这道题的神奇之处在于一次从左到右的线性遍历就足够解决环形问题根本不用取模。很多人一看到环形就开始 (i 1) % gasSize把问题复杂化了。取模是在暴力模拟时才需要的东西贪心解法里完全用不到。4. 贪心为什么是对的严格证明与常见误区4.1 断点重选的严格证明思路很多人能背下代码但一旦被面试官追问为什么 start 可以直接跳到 i 1就卡壳。这里给一个相对严谨但不复杂的证明建议看完后能自己复述出来。假设当前候选起点是 s我们从 s 出发累加 cur到位置 i 时首次出现 cur 0。cur 0 的意思是sum(gas[s..i]) - sum(cost[s..i]) 0这已经说明 s 不能作为全局起点。现在要证明 s 到 i 之间的任意一个位置 ks k i也不可能作为全局起点。从 k 出发到 i 这段路的净剩余是sum(gas[k..i]) - sum(cost[k..i])把它拆成两部分[sum(gas[s..i]) - sum(cost[s..i])] - [sum(gas[s..k-1]) - sum(cost[s..k-1])]第一个中括号里的东西是负数因为这是 cur 0。第二个中括号里的东西是什么呢是从 s 到 k-1 的净剩余。因为 i 是第一次出现 cur 0 的位置所以在 i 之前的所有位置cur 都大于等于 0尤其是 k-1 处也大于等于 0。也就是说第二个中括号是非负数。负数减去一个非负数结果必然是负数。所以从 k 出发到 i 时油量就已经是负数了k 不可能完成整圈。这就证明了 s 到 i 之间的所有点都可以一次性淘汰start 直接设为 i 1 是安全的。上面的证明里i 是第一次出现 cur 0 的位置这个条件很关键。实际上我们的代码里cur 0 时立即重置所以每次触发重置时的 i 正是当前区间内的第一次负值点证明始终成立。4.2 三个经常让人困惑的误区误区一觉得贪心可能会漏解。有人会担心万一 start 跳过的那段里有一个点虽然到 i 时会断油但它有别的办法绕一圈不可能。因为绕一圈必须经过 i而证明里说了从那任何一点出发到 i 就已经破产谈不上绕一圈。所以不会漏解。误区二认为 total 0 是充分条件。注意total 0 只是必要条件里的总账单独有它还不够你还需要一个正确的起点。比如 gas [2, 0, 0], cost [0, 1, 1]total 恰好等于 0但如果你从下标 1 出发就不行必须从 0 出发。贪心算法做的是两件事先用 total 判断有没有解再用 cur 和 start 找出那个正确的起点。误区三担心最后需要再模拟一次确认。其实不需要。最后一次触发 cur 0 之后start 到数组末尾这段路上 cur 一直非负说明从 start 出发能撑到数组末尾而前面被裁掉的那些区间总亏损是被 start 之后积累的正剩余覆盖的因为 total 0。这两个条件合在一起已经足以保证整圈可行。4.3 和暴力解法的性能对比为了直观看差距我整理了一个简单的估算表。这里假设每次遍历只做一次简单的加减比较按现代 CPU 每秒约 10^8 次基础运算估算。输入规模 n暴力 O(n^2) 估算耗时贪心 O(n) 估算耗时100约 0.0001 秒约 0.000001 秒10^4约 1 秒约 0.0001 秒10^5约 100 秒约 0.001 秒10^7约 10^7 秒约 115 天约 0.1 秒LeetCode 上这题的数据规模一般在 10^5 级别暴力解法超时是板上钉钉的事。实际提交时贪心解法在 C 语言下运行时间基本都是 0ms而同样用贪心思路用 Python 写也就是几十毫秒的事。这就是算法复杂度带来的本质差别。空间上两者都是 O(1)贪心并没有消耗额外数组这也很符合 C 语言追求简洁高效的气质。5. 延伸思考这题的工程启发与刷题建议5.1 环形数组处理技巧从这道题能带走什么加油站问题是典型的环形数组 累计量题型。处理环形数组有三板斧第一种是双倍数组展开把环形变成线性但需要额外空间第二种是取模索引在不扩容的情况下模拟环但要注意边界第三种是前缀和/累计量的思想先跑一遍线性再利用总量关系处理环形这道题用的就是这种思路。掌握了第三种思路对其他环形题目也很有帮助。比如 LeetCode 918 环形子数组的最大和核心就是把环形最大和拆成两种情况一种是不跨越边界的普通最大子数组和另一种是跨越边界的总和减去最小子数组和。理解加油站问题里总量 局部累计量的配合再看 918 就顺滑很多。另外这道题和 LeetCode 53 最大子序和也有神似之处。最大子序和里的贪心做法是累加 cur一旦 cur 小于 0 就把它重置为 0重新开始累加。加油站问题里的 cur 也是一样的逻辑只不过多了一个 start 来记录候选起点。建议先做 53再做 134会有一种原来是同一个套路的顿悟感。5.2 什么时候该想到贪心几个信号很多初学者拿到算法题分不清该用动态规划、贪心还是二分。根据我自己的刷题经验遇到这类在一堆起点/选择里找一个可行起点的题可以按下面的信号来判断。如果题目存在一个一票否决条件比如这里的总油量小于总消耗就无解那贪心的概率就很大。如果每次排除一个选择时能一次性排除一大段不可能的区域那也往往是贪心。如果一个问题满足局部最优能推导全局最优的性质那就大胆用贪心。贪心和动态规划最大的区别在于动态规划需要存储子问题的最优解通常要开数组贪心往往只维护几个变量边走边决策不回头。加油站问题里你会发现每一步决策只需要当前信息和几个累计值不需要查表这就是典型贪心。而 LeetCode 55 跳跃游戏、LeetCode 435 无重叠区间也都是类似的贪心练习建议一起刷。5.3 给 C 语言初学者的刷题建议如果你刚开始用 C 语言刷题可能对 LeetCode 提交函数、本地自己写 main 的这种模式不太习惯。几个小建议可以参考。第一先把数组、指针、函数传参基本功打牢。C 语言刷题的核心就是数组操作gas 和 cost 都是以指针形式传入的你要习惯使用 *gas 和 gas[i] 的等价关系。第二本地环境建议用 VS Code 配好 C 语言编译调试环境快捷键编译运行再用 printf 或调试器观察 cur 和 start 的变化。第三如果看不懂某个算法的正确性不要硬背代码画图是最好的方式。你可以把 gas[i] - cost[i] 的走势图画在纸上看一眼就会发现 cur 跌到 0 以下的地方就是需要跳 start 的地方非常直观。刷题初期不要追求题量追求每道题彻底搞懂。像这题能把证明过程复述出来、能把暴力解法改成贪心解法、能分析两个解法的复杂度差异就算真正吃透了。有了这种深度面试手写算法题时考官追问任何一个细节你都不慌。我个人刷这题时最大的体会是贪心算法看起来短平快但一旦问起正确性很多人就露怯。千万不要因为代码短就轻视它把上面的证明吃透比多刷十道简单题更有价值。最后再分享一个调试小技巧如果你在某次测试中结果不对别急着看答案把每个位置的 diff 和 cur 打印出来盯着 cur 第一次变负的位置看你会立刻明白算法在哪里做出了抛弃区间的决策。这个习惯帮我解决了不止一道贪心题的问题。