LeetCode 134. 加油站 java题解

https://leetcode.cn/problems/gas-station/description/

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int len=gas.length;
        int a=0,b=0;
        for(int i=0;i<len;i++){
            a+=gas[i];
            b+=cost[i];
        }
        if(a<b) return -1;//不够
        //够。要找起点
        int cur=0;
        int start=0;
        for(int i=0;i<len;i++){
            cur+=(gas[i]-cost[i]);
            if(cur<0){//当前位置无法到下个位置，无法前进
                cur=0;
                start=i+1;
            }
        }
        return start;
    }
}

总的加油量大于等于总耗油量。为什么 total_tank 大于等于0 就说明总加油量是够的？

• 从实际意义理解：每一个 gas[i] - cost[i] 表示在第 i 个加油站加油后，到下一个加油站时油量的净变化。如果把所有这些净变化累加起来得到 total_tank >= 0，就说明在整个环形路线上，车辆在各个加油站加油后，整体上是有足够的油量来支持完成一圈行驶的。即使在某些局部路段，车辆可能出现油量不足的情况（即 current_tank < 0），但从全局来看，通过合理选择起点和在其他加油站的加油，最终是能够绕一圈的。

举个简单的例子，如果有三个加油站，gas = [3, 5, 1]，cost = [2, 4, 2]，计算可得 total_tank = (3 - 2) + (5 - 4) + (1 - 2) = 1 + 1 - 1 = 1 >= 0。这表明虽然从第三个加油站出发单独看是无法开到下一个加油站的（因为 1 - 2 = -1 < 0），但综合三个加油站的情况，总加油量是足够完成一圈行程的，实际上从第一个加油站出发就可以绕一圈。