LC134. 加油站

题目描述

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。 如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。 说明: 如果题目有解，该答案即为唯一答案。 输入数组均为非空数组，且长度相同。 输入数组中的元素均为非负数。

题目解析

题目在说什么

想象你开着一辆车在一条环形公路上，公路上有 N 个加油站。每个加油站能给你加一定量的油（gas[i]），但开车到下一个加油站需要消耗一定量的油（cost[i]）。你的车油箱无限大，但一开始是空的。你要找一个加油站作为起点，从那里出发，沿着环路开一圈，最后回到起点，并且中途不能因为没油而抛锚。如果能找到这样的起点，就返回它的编号；如果所有起点都不行，就返回 -1。

题目还给了几个重要提示：

• 如果有解，答案只有一个。
• 所有加油站的油量和消耗都是非负数（不会出现负油量）。
• 两个数组长度相等。

思路是怎么来的

第一步：先判断“总油量够不够”

我们先把所有加油站的油加起来，再减去所有路段消耗的油。如果总油量小于总消耗，那无论从哪个加油站出发，最后都会没油，因为整圈下来油是净亏的。这就像你兜里只有100块，但一圈路费要120块，你肯定走不完。所以，如果总油量 < 总消耗，直接返回 -1。

第二步：如果总油量够，怎么找起点？

现在总油量够，但起点选错还是可能中途没油。比如你从油量少的站出发，可能开到一半油不够了。

关键观察：假设我们从加油站0开始，一路开到加油站k，发现油不够了（也就是从0到k这段，累计油量 < 累计消耗）。那么，从0到k之间的任何一个加油站出发，也都无法顺利通过k这个点。为什么？因为如果你从中间的某个站i出发，你出发时的油量更少（因为少了前面站的油），而消耗是一样的，所以更不可能通过k。所以，我们可以直接跳过0到k这些站，尝试从k+1站开始。

这个思路就像：你从起点开始跑步，跑到某个点跑不动了，那说明起点到那个点之间的任何一个位置作为起点，你都会在那个点跑不动。所以不如直接跳到那个点的下一个位置重新开始。

第三步：用数学证明为什么这样跳一定能找到解

题目给的解析用数学归纳法证明了：如果总油量 >= 总消耗，一定有解。简单理解就是：总油量够，就相当于你有一笔“总预算”，只要找到合适的起点，就能让预算在每一段都非负。而上面的跳跃方法正好能保证找到这个起点。

代码逐步拆解

我们来看参考代码，一步一步解释。

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;  // 加油站数量
        int remainGas = 0;   // 用于统计总油量 - 总消耗

第一步：检查总油量是否够

        for (int i = 0; i < n; i++) {
            remainGas += gas[i] - cost[i];
        }
        if (remainGas < 0) {
            return -1;
        }

这里把每个站的加油量和消耗量相减，然后累加。如果最终结果小于0，说明总油量不够，直接返回-1。这个判断很简单，但很重要，因为如果总油量不够，后面就不用找了。

第二步：找起点

        int currentGas = 0;  // 当前油箱油量
        int i = 0;           // 当前尝试的起点
        int index = 0;       // 最终选定的起点

初始化：从第0个加油站开始尝试，当前油量为0，记录起点为0。

        while (i < n) {
            currentGas += gas[i] - cost[i];  // 从i出发，开到i+1，油量变化
            if (currentGas >= 0) {
                i++;  // 油量够，继续往前开
            } else {
                // 油量不够，说明从当前起点到i这段不行
                currentGas = 0;      // 重置油量
                index = i + 1;       // 尝试从下一个加油站开始