加油站 图解题解

环形加油站，求哪个站能发车绕一圈

n 个加油站围成一圈，第 i 站能加 gas[i] 升油，从第 i 站开到下一站耗 cost[i] 升，油箱起初为空。挑一个站作起点绕一圈，绕回原点就返回它下标，绕不完返回 -1。题面 gas=[4,5,2,6,1,3,7,2,5,4,8,3]、cost=[6,3,5,2,7,2,1,8,3,2,4,6]，答案是下标 5。

每个站都试一次当起点，慢在哪

把每个站轮流当起点、模拟开一圈，中途油箱不跌到负就算能绕完。12 个站要试 12 趟、每趟走满一圈，n 个站是 n×n 次操作、也就是 O(n²)。很多起点刚开出去就断油，却还陪着走完才判出局。

总量定生死，跌负点之后才是真起点

先算每站的净油量 net[i]=gas[i]−cost[i]。全部加起来是总净油量，它若为负，说明全程油不够耗、哪都开不完，直接 -1；本题总净油量 +1、非负，可行起点一定存在。

有解后再定它落哪。从某个起点累加 net，油箱非负就往下走；一旦某站油箱跌成负数，说明这个起点到当前站整体是亏的。这中间每一站也当不了起点：从中途某站另起，等于丢掉前面那段净油——那段没让油箱提前跌负、必然非负，丢掉只会更早断油。所以这一段起点全排除，候选直跳到跌负站后一位、清零重攒，起点只前移不回退。

三个变量，一遍扫完就定起点

落到代码就三个变量：total 累加全程净油量、只用来判有无解；tank 是当前起点出发后的油箱；start 记候选起点、从 0 起。遍历每站，total 和 tank 都加这站的 net，一旦 tank 跌成负数，就让 start 跳到 i+1、tank 归零。扫完一趟，total≥0 就返回 start，否则 -1。

题面这 12 个站，start 怎样被逼到 5

净油量依次 −2、+2、−3、+4、−6、+1、+6、−6、+2、+2、+4、−3，加起来 +1、有解。start=0、tank=0 开扫。站 0 加 −2 得 −2 跌负，start 跳到 1、清零。站 1 加 +2 得 2。站 2 加 −3 得 −1 又跌负，start 跳到 3、清零。站 3 加 +4 得 4。站 4 加 −6 得 −2 第三次跌负，start 跳到 5、清零。

从站 5 起没再跌过：站 5 加 +1 得 1，站 6 加 +6 得 7，站 7 加 −6 得 1，站 8 加 +2 得 3，站 9 加 +2 得 5，站 10 加 +4 得 9，站 11 加 −3 得 6。start 停在 5，total 也累到 +1、非负，返回下标 5。

起点是跳不是挪，别踩这几个坑

最坑的是把跳转当逐格挪：tank 跌负时只让 start 挪一格，等于没吸取 start..i 整段都不可行、白试几趟还停在错起点，得一步跳到 i+1。跳完忘清 tank，新起点会背着上段亏账越加越偏。还有拿 tank 判有没有解也错——它被清过零、只反映当前段，得看累到尾的 total。

复杂度上，只从左到右扫一趟、每站常数次运算，时间 O(n)，把暴力那圈套圈的 O(n²) 压平；只用三变量，空间 O(1)。

Python

def canCompleteCircuit(gas, cost):
    total = 0      # 总净油量，判有没有解
    tank  = 0      # 当前候选起点出发后的油箱
    start = 0      # 当前候选起点
    for i in range(len(gas)):
        net = gas[i] - cost[i]   # 这站净油量
        total += net
        tank  += net
        if tank < 0:             # 油箱见底
            start = i + 1        # 起点跳到下一站
            tank  = 0            # 清零重新攒
    return start if total >= 0 else -1

C++

int canCompleteCircuit(vector<int>& gas, vector<int>& cost){
    int total = 0, tank = 0, start = 0;
    for(int i = 0; i < gas.size(); i++){
        int net = gas[i] - cost[i];   // 这站净油量
        total += net;
        tank  += net;
        if(tank < 0){                 // 油箱见底
            start = i + 1;            // 起点跳到下一站
            tank  = 0;                // 清零重新攒
        }
    }
    return total >= 0 ? start : -1;
}

Java

public int canCompleteCircuit(int[] gas, int[] cost) {
    int total = 0, tank = 0, start = 0;
    for (int i = 0; i < gas.length; i++) {
        int net = gas[i] - cost[i];   // 这站净油量
        total += net;
        tank  += net;
        if (tank < 0) {               // 油箱见底
            start = i + 1;            // 起点跳到下一站
            tank  = 0;                // 清零重新攒
        }
    }
    return total >= 0 ? start : -1;
}