先说我个人的判断LeetCode 134 这道题是一个看起来不难但第一次做大概率写不出最优解的典型。很多人第一眼以为就是模拟跑圈然后写了个 O(n²) 的枚举样例过了一提交直接超时。也有的人背过答案能写出那个一遍循环的贪心解法但被追问为什么从累计和为负的下一个位置开始就是答案时就讲不清楚了。这篇文章并不是单纯给你一份能通过的标准代码而是把这道题背后的环形数组处理思路、贪心正确性论证、以及它可以辐射出去的相关题型全部理顺。无论你是准备面试想彻底搞懂还是刷题想形成自己的方法论都值得把这篇看完。1. 环形队列与油箱存量题目到底在说什么1.1 先还原一个可执行的问题描述题目本身不复杂但我发现很多人一开始就被环形两个字干扰了。直接说人话有一条环形公路上面均匀分布着n个加油站编号从 0 到 n-1。每辆车有个油箱容量无限大这个条件很关键初始时油箱是空的。你从某个加油站出发可以在该站加gas[i]升油然后开车到下一个加油站路上要消耗cost[i]升油。问是否存在一个加油站作为起点使得这辆车能够绕着环形公路走一整圈最终回到起点。注意一个问题我们从第 i 站出发时油箱是空的也就是说你必须在第 i 站先把油加上然后才有油开往第 i1 站。我见过有人误以为出发时油箱自带一定油量这就把题目条件凭空改掉了。题目要求返回一个可行的起点下标如果不存在返回 -1。题目保证解如果存在则唯一后面讲为什么唯一这也是它能用贪心直接做的隐含条件之一。1.2 输入规模决定你能走多远老规矩先看约束。gas 和 cost 都是长度为 n 的整数数组n 的范围通常到 10^4 甚至 10^5gas[i] 和 cost[i] 都是非负整数。这个规模传递了一个很明确的信息O(n²) 的暴力解法在真实数据下一定会超时你的目标必须是 O(n) 时间、O(1) 额外空间的算法。事实上这道题的最优解就是这么干净——一趟循环就出答案。这里补充一个经常会考到的点如果把每个加油站往下看你会发现 gas[i] - cost[i] 才是本质数据。加 100 升油跑 80 公里和加 10 升油跑 0 公里对能否走完这个问题来说起作用的只是净收益gas[i] - cost[i]。后面所有推导都建立在这个净收益数组上这是理解本题的第一步。2. 暴力枚举的时间账n² 解法为什么活不过样例2.1 模拟一次完整跑圈先别急着上最优解把暴力思路捋清楚其实很有价值因为为什么不能暴力本身就解释了贪心跳跃的必要性。暴力做法非常直接枚举起点 i从 i 开始模拟跑一圈。维护一个当前油量 cur初始为 0。走到第 j 个加油站时先加gas[j]再减cost[j]如果 cur 在任何时刻小于 0说明这个起点不行换下一个起点。以题目自带的例子来说gas [1, 2, 3, 4, 5] cost [3, 4, 5, 1, 2]从 0 号站出发在 0 站加 1消耗 3cur -2直接失败。从 3 号站出发在 3 站加 4消耗 1cur 3到 4 站加 5消耗 2cur 6回 0 站加 1消耗 3cur 4到 1 站加 2消耗 4cur 2到 2 站加 3消耗 5cur 0一圈走完回到 3 号起点成功。所以答案是 3。这个过程直观、零思考只要你会模拟就能写。但它的问题也很明显最坏情况下每个起点都要走一整圈时间复杂度是 O(n²)空间复杂度 O(1)。2.2 复杂度的现实冲击n 10^4 时n² 10^8勉强能压在 C 的时间极限边沿n 10^5 时n² 10^10基本是放弃治疗了。LeetCode 判题数据可不会给你留这种情面暴力就是超时。但暴力解里有一个值得注意的细节**一旦中间某一步 cur 变负你其实已经知道这个起点是失败的了再继续模拟后面的加油站毫无意义。**这个点听上去像废话但最优解的灵感恰好就藏在这里。所有高效的连续性问题求解本质上都在做同一件事如何把失败信息利用起来避免重复计算。本题的 O(n) 解法就是把cur 变负这个失败信息变成了跳跃的凭据。3. 贪心解法的本质找出数组的最低点3.1 把加油和耗油换算成净收益先定义净收益数组rest[i] gas[i] - cost[i]它可以看成你每次经过一个加油站时油量的净变化。如果 rest[i] 为正说明这个站是活的油越跑越多如果为负则是消耗站。然后看整趟能不能走完的必要条件total sum(rest[0] ... rest[n-1])如果 total 0说明整圈总的耗油量大于总的加油量。油箱容量再大也没用任何起点都不可能完成一圈。所以 total 0 时直接返回 -1。这是一个很朴素但必须先检查的条件它也为后面的贪心做了铺垫。如果 total 0接下来就是找从哪里出发的问题。3.2 核心性质一旦累计为负前面全部作废假设我们从起点 start 出发维护一个当前累计净收益 cur可以理解为当前油箱里的油量。我们从 start 一直走到某个加油站 i此时 cur 0意味着从 start 到 i 这一段汽车已经完全透支还没到 i1 就已经撑不住了。这时候能得到一个特别强力的结论区间 [start, i] 内部的任何一个加油站都不能作为合法起点走完全程。为什么因为 cur 是一个累加和它在绝大多数时候是缓慢爬升又跌落的过程在跌破 0 之前cur 一度没有小于 0。也就是说对于区间 [start, i] 里的任意一个点 k从 start 走到 k 的时候油箱里还有油恒大于等于 0。现在假设我们放弃 start改从 k 出发那么在 k 这个位置油箱是空的等于把从 start 到 k 累积起来的那部分正的油量给丢了。起点都少了油后面能撑到 i 就已经很勉强甚至可能在更早的位置就失败了反正不可能比从 start 出发撑得更远。生活里有个很接近的类比你背着一桶水从村子出发往山上送水走到半山腰时水已经喝光了那么中途任何一个你当时还有水的点其实都不适合作为满状态出发的新起点因为从那里出发你手里的水只会更少。所以策略就变成了一旦 cur 在 i 处跌破 0直接承认 [start, i] 整个区间是废段下一个可能的起点直接跳到 i1然后 cur 清零重来。这就是贪心跳跃的核心。3.3 为什么答案是从最低点出发再往下挖一层这个跳跃过程其实在做一个非常数学化的事情寻找前缀和的最小值点。定义前缀和P[-1] 0 P[k] rest[0] rest[1] ... rest[k]cur 从 start 开始累加其实是在计算P[i] - P[start-1]。cur 0 等价于P[i] P[start-1]。也就是说触发跳跃的时刻正是我们找到了一个比之前前缀和更小的新低点。等到整趟扫描结束start 所指向的位置一定是前缀和最小值出现位置的下一个下标。而前面我们已经判断过 total 0所以环形路径上从最低点出发无论走到哪里累计净收益都不会低于 0。这个结论带来了一个非常优美的抽象本题根本不需要遍历所有起点再排除它本质上就是在问前缀和的最低点出现在哪里。一旦找到它从它之后开始总能在任何时刻维持非负油量走完一圈。4. 两行判断加一个循环代码落地与边界推敲4.1 Python / C / Java 实现理解了前面的证明代码其实短到令人意外。核心结构就一个循环循环里做两个累加、一个判断。下面是 Python 版本class Solution: def canCompleteCircuit(self, gas: List[int], cost: List[int]) - int: n len(gas) total 0 # 整个环路的净收益 cur 0 # 从当前候选起点开始的净收益 start 0 for i in range(n): diff gas[i] - cost[i] total diff cur diff if cur 0: # [start, i] 这一段已经没戏起点直接跳到 i1 start i 1 cur 0 return start if total 0 else -1C 版本逻辑完全一致class Solution { public: int canCompleteCircuit(vectorint gas, vectorint cost) { int n gas.size(); int total 0, cur 0, start 0; for (int i 0; i n; i) { int diff gas[i] - cost[i]; total diff; cur diff; if (cur 0) { start i 1; cur 0; } } return total 0 ? start : -1; } };Java 也顺手贴一下三者没有本质区别class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { int n gas.length; int total 0, cur 0, start 0; for (int i 0; i n; i) { int diff gas[i] - cost[i]; total diff; cur diff; if (cur 0) { start i 1; cur 0; } } return total 0 ? start : -1; } }三个版本都是 O(n) 时间复杂度、O(1) 空间复杂度。我个人的观点是这道题的代码属于标准答案肌肉记忆级别刷题时应该能闭着眼写出来但比写代码更重要的是把第 3 节的证明吃透。4.2 边界条件与常见翻车现场第 4.1 节代码看着短但实际写的时候有四个边界场景我把踩过的坑和正确的处理一起列出来边界场景出错方式正确处理total 0没检查 total直接返回 start必须最后判断 totaltotal 0 返回 -1起点跳到 n忽略 start i1 可能等于 n正好等于 n 时说明合法起点在环的终点实际上对应下标 n-1 之后的 0即只要 total 0 就返回 startstart 可能是 n 吗回头细说cur 0 时用 cur 0 重置忘记清零导致后面的累计被前面失败段污染cur 必须清零这是跳跃的状态割裂数组长度为 1有些人会写成特判根本不需要特判循环一轮天然处理很多人容易忽略的是 start 可能等于 n 的情况。但注意循环里如果 cur 0 且 i n-1那么 start n这看起来越界了。然而此时 total 必然小于 0因为最后一段的净收益为负且总收益不可能为正所以会被total 0这个判断拦住返回 -1。如果 total 0那么最后一个位置触发cur 0是不可能发生的。所以根本不用担心 start 越界。这是我当年第一次写这道题时纠结过的地方实际上代码的先后顺序已经天然规避了这个问题。另外题目说的是油箱容量无限大所以只要累计净收益不跌到 0 以下就永远不会抛锚。这意味着判断条件是cur 0而不是cur 0。如果某一次你恰好把油耗到 0恰好到达下一个加油站这仍然是合法的因为到站后你又可以加油往前走了。这个细节在两个示例里其实都有体现示例 1 从 3 出发跑完一圈回到 3 时cur 正好等于 0依然算成功。5. 正确性证明并不是可有可无的仪式5.1 必要性与充分性的拆解LeetCode 的题解区从来不缺代码但真正拉开差距的是证明。面试时如果你只会写代码却说不出理由面试官几乎一定会追问到底。很多人栽在这道题上不是代码写不出来而是为什么贪心成立讲不明白。我们分两步来证明必要性如果 total 0任何起点都不可能成功。因为跑完一整圈的净收益总和为负无论从哪开始最终回到起点时油箱油量必然比出发时少而出发时油箱是空的所以一定在中途就抛锚。充分性如果 total 0那么按照算法的跳跃规则找到的 start 一定可行。必要性没什么争议难点是充分性。5.2 前缀和视角的一步到位证明把前缀和的定义再拿过来P[-1] 0 P[k] rest[0] ... rest[k]算法的跳跃条件是 cur 0。cur 从 start 开始累加当 cur 0 时说明P[i] - P[start-1] 0即P[i] P[start-1]。此时把 start 更新为 i1等价于把更小的前缀和P[i] 作为新的基准。于是扫描完整个数组后start 满足P[start-1]是数组 P[-1], P[0], ..., P[n-1] 中的最小值。现在从 start 出发走到任意一个加油站 j分两种情况如果 j start此时累计净收益为P[j] - P[start-1]。因为P[start-1]是全局最小值所以这个差值大于等于 0一路上不会抛锚。如果 j start相当于先走完整个后半段到达数组末尾再绕回到数组开头继续走。累计净收益为(P[n-1] - P[start-1]) P[j]。由于 total P[n-1] 0且P[j] P[start-1]所以这个值也大于等于 0。两种情况合在一起证明完全成立。这就是从最低点出发的数学表达。这个证明干净利落面试时当场推导一遍比背任何模板都有说服力。这也是为什么题目保证如果有解则答案是唯一的——因为前缀和的最小值点是唯一的除非有并列最小值但并列时从最后一个最小值之后出发才能保证全程非负所以实际答案依然唯一。5.3 拿示例手撕一遍再回到示例 1gas [1, 2, 3, 4, 5] cost [3, 4, 5, 1, 2] rest [-2, -2, -2, 3, 3]计算前缀和P[-1] 0 P[0] -2 P[1] -4 P[2] -6 P[3] -3 P[4] 0P[-1..4] 里的最小值是 P[2] -6start 2 1 3。答案就是 3。示例 2gas [2, 3, 4] cost [3, 4, 3] rest [-1, -1, 1]total -1 0直接返回 -1。完全不需要进入找起点环节。这两个示例再次印证这道题的本质就是在找前缀和的最低点。6. 从这道题延伸出去的路标6.1 同构问题环形数组最大子段和掌握了环形数组找最低点这个手法你会发现它在很多题目里都有影子。最直接的是 LeetCode 918 环形子数组的最大和。那道题要求在一个环形数组里找一个连续子数组使和最大。常见解法有两种情况一最大子段和不跨越数组首尾直接对普通数组跑 Kadane。情况二最大子段和跨越首尾等价于总数减去数组的最小子段和而最小子段和可以用跑 Kadane 时对和取相反数来求或者改成求最小子段和的贪心。这个思路里的最小子段和和本题的前缀和最低点气质非常接近。两道题一起刷会明显提升你对环形数组切割这一类问题的敏感度。6.2 进阶变体要求返回最小初始油量如果把题目改一改不指定起点而是问你至少要带多少油出发才能保证从某个加油站开始可以跑完一圈甚至改成从任意加油站出发都可以这时候可以用一个更强的结论假设我们维护一个从固定起点比如 0 号站开始的前缀和序列要保证全程油量非负初始油量至少是所有前缀和最小值的相反数。这个结论本质上和本题的证明是一回事只不过把找起点换成了算初始油量。很多公司的笔试和竞赛题喜欢这样变形其实内核完全没变关键在于你能否识别出前缀和最低点这个关键词。6.3 面试与竞赛中的贪心识别最后说一点竞赛实战层面的经验。做多了你会发现只要题目出现类似环形路径每站有增有减判断能否走完一圈的一类描述优先往以下三个方向去想先算总和总和为负直接无解这是最快能排除一半情况的检查。尝试把环形展开成线性找一个断点使线性路径上任意前缀和都非负。一旦发现线性路径中途前缀和为负就立刻跳跃到失败点的下一个位置重新开始而不是从头枚举。这个失败即跳跃的模式其实在很多贪心题里都会出现。比如判断一个数组能否被划分为若干满足条件的段或者找最长可行区间的双指针思路都在用类似的失败信息复用逻辑。把 Gas Station 想透等于给这一族问题都打了一个地基。我个人刷题时的习惯是看题解从不只记代码而是把证明在草稿纸上独立推导一遍。这道题的核心证明——P[start-1]是前缀和最小值——我会要求自己在三天后还能默写出来。能独立写出来才是真正消化了。如果看完这篇文章你也能做到这一点那这道题才算真正拿下了。