这道题看起来像是一个普通的环形数组模拟题，很多小伙伴一开始都是顺着物理直觉去写代码，结果却常常在“超时（TLE）”的边缘疯狂试探。今天我们就来一步步拆解这道题，看看如何通过图解指针的移动来发现跳跃规律。

---

一、直觉模拟与“跳跃”优化的图解

拿到这道题，最直观的思路就是暴力枚举：把每一个站都当成起点试试，内部再开一个循环，顺着开下去，看能不能走回起点。

但如果只是纯暴力，时间复杂度是 O(N^2)，必定超时。所以我们需要找到一个优化点。

假设我们在考虑将 i 作为起点，初始化 j = i。我们用 * 代表加油站，来看看指针是如何移动的：

假设当前在考虑 i，先初始化 j = i
*  *  *  *  *  *
^
i
^
j

随后 j 会不断向后移动（也就是车一直往前开）：

随后 j 会进行后移
*  *  *  *  *  *
^  ^
i  j

继续后移...
*  *  *  *  *  *
^        ^
i        j

【核心优化定律来了】

当考虑 i 能到达的最远的时候，假设是 j。

那么 i + 1 到 j 之间的节点是不是就都不可能绕一圈了？

假设 i + 1 的节点能绕一圈，那么就意味着从 i + 1 开始一定能到达 j + 1。

又因为从 i 能到达 i + 1，所以从 i 也能到达 j + 1。

但事实上，i 最远到达 j 。产生矛盾，所以 i + 1 的节点一定不能绕一圈。同理，其他的也是一样的证明。

所以下一次的 i 我们不需要从 i + 1 开始考虑，直接从 j + 1 开始考虑即可。

优化跳跃：既然 i 到 j 之间都不行，i 直接跳到 j 的下一个位置开始考虑！
*  *  *  *  *  *
            ^
            i
            ^
            j

还有一种情况，就是因为到达末尾的时候，会回到 0。

如果对于下边的情况。

还有一种情况，就是因为到达末尾的时候，会回到 0。

如果对于下边的情况。

* * * * * *
  ^   ^
  j   i
如果 i 最远能够到达 j ，根据上边的结论 i + 1 到 j 之间的节点都不可能绕一圈了。
想象成一个圆，所以 i 后边的节点就都不需要考虑了，直接返回 -1 即可。

---

二、Python 选手的隐藏“天坑”

按照上面的图解思路，逻辑非常完美。于是，很多 Python 小伙伴大笔一挥，写下了这样的代码，试图实现 i 的跳跃(包括我)：

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n = len(gas)
        for i in range(n):
            j = i
            remain = gas[i]
            
            # 不断向后开，直到油不够
            while (remain - cost[j] >= 0):
                remain = remain - cost[j] + gas[(j + 1) % n]
                j = (j + 1) % n
                if j == i: 
                    return i
                    
            if (j < i): 
                return -1
            
            # 【核心优化】：i 直接跳到 j，外层 for 循环 i++，相当于从 j+1 开始
            i = j  
            
        return -1

结果：超时（TLE）

为什么会这样？

这就是 Python 语言特有的一个“暗坑”。在 Python 中，for i in range(n): 的底层逻辑是一个迭代器，每次循环都会强制从 range 里取出下一个连续的数字覆盖 i。这就意味着，哪怕你在循环体里写了 i = j，到了下一次循环，i 依然会被强行重置回老老实实的递增状态。

你的“跳跃优化”完全失效了，代码又退化成了 O(N^2) 的暴力解法。

如何破解？

如果想手动控制步长跳跃，请一定使用 while 循环！

        # 正确的跳跃写法
        i = 0
        while i < n:
            # ... 内部逻辑不变 ...
            
            # 核心优化：直接让 i 跳到 j + 1
            i = j + 1 

---

三、贪心的本质：“能量守恒”视角

其实，跳跃优化的本质，已经非常接近这道题的最优解了。我们可以跳出模拟的思维，用“全局与局部”的贪心视角来看待这道题，代码会变得不可思议的简单。

有两个非常核心的推论：

1. 推论 1（全局能量守恒）： 如果所有的 sum(gas) < sum(cost)，那么不管你怎么选起点，整个系统的油根本不够跑一圈，绝对无解，直接返回 -1。

2. 推论 2（局部排除法）： 如果我们在跑的过程中，累计的油量 current_gas < 0 了，说明什么？说明从刚才的起点到当前站 i 这一段路是“亏本”的。如前面图解所说，这期间的任何一站都不能做起点。真正的起点，只能在 i + 1 站（或者更往后）。

结合这两个推论，我们甚至不需要去模拟转圈圈，只需要一次遍历：

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        # 1. 能量不守恒，直接判死刑
        if sum(gas) < sum(cost):
            return -1
            
        current_gas = 0
        start_index = 0
        
        # 2. 寻找真正的起点
        for i in range(len(gas)):
            current_gas += gas[i] - cost[i]
            
            # 如果中途没油了，说明从 start_index 到 i 都不能做起点
            if current_gas < 0:
                start_index = i + 1  # 候选起点推迟到下一站
                current_gas = 0      # 油箱清零，重新开始累加
                
        return start_index

---

四、极致优化：C 单次遍历 (One-Pass)

在上面的 Python 代码中，sum(gas) 和 sum(cost) 已经遍历了一次数组，加上后面的 for 循环，总共遍历了两次。

为了追求极致的性能，我们可以将这两次遍历合并为一次（One-Pass）。

我们用 total_surplus 记录全局的油量盈亏，替代 sum() 的作用：

int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize) {
    int total_surplus = 0;   // 记录全局：总加水量 - 总消耗量
    int current_surplus = 0; // 记录局部：当前考察起点的油量盈亏
    int start_index = 0;     // 记录候选起点

    for (int i = 0; i < gasSize; i++) {
        int diff = gas[i] - cost[i];
        
        // 同时累加全局和局部
        total_surplus += diff;
        current_surplus += diff;

        // 【图解逻辑】：局部油量成负数，当前区间报废，跳跃到下一站！
        if (current_surplus < 0) {
            current_surplus = 0; // 局部油箱清零
            start_index = i + 1; // 起点顺延到下一站
        }
    }

    // 只要全局油量盈余 >= 0，就一定能跑完一圈
    return total_surplus < 0 ? -1 : start_index;
}

五、总结

从最开始的指针模拟，到通过图解发现“跳跃区间”的规律；再到掉进 Python for 循环的语言特性陷阱；最后跳出局限，用全局“能量守恒”视角写出 O(N) 的贪心解法。

大家也可以去看看卡哥的代码随想录

134. 加油站 | 贪心算法 | 剩余油量累加和 | 代码随想录-全网最全算法数据结构刷题学习路线|图文+视频教程|免费开源

本博客的思想来自于力扣134题解的windliang大佬