加油站问题（贪心）

题目：

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

示例 1:

输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

示例 2:

输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。

题意：开车从某个站点出发，初始油量为 000，到达一个站点就可以补充油量，两个站点之间需要消耗油量，求从哪个站点开始能环游一圈。

汽车的油箱容量无穷，所以到达某个点时一定会将该站点的油全部加上，这是一种贪心的思想，毕竟想要全程旅游，油越多越好。

暴力的做法就是枚举起点，从它开始遍历全部站点进行尝试。站点的总数为 nnn，规定 n≤105n\leq 10^5n≤105，这种 O(n2)O(n^2)O(n2) 的操作会超时。

贪心

首先必须明确，从一个站点 iii 出发前，可以补充该站点的油量 gas[i]gas[i]gas[i]；从该站点出发到达下一个站点，会消耗油量 cost[i]cost[i]cost[i]。

因此，完全可以将它们 捆绑 进行理解。环游一圈，对应 nnn 次加油与 nnn 次耗油。将 gas[i]−cost[i]gas[i]-cost[i]gas[i]−cost[i] 记为 diff[i]diff[i]diff[i]。

如果从第 iii 个站点到达第 i+1i+1i+1 个站点时，对应的 diff[i]<0diff[i]<0diff[i]<0，那就说明第 iii 个站点一定不能作为起点，因为第一段旅途都完成不了！

所以，为了方便表述 ，将 diff[i]<0diff[i]<0diff[i]<0 的第 iii 个位置看作一个“大坑”。这个坑的前面这个第 iii 点一定不能作为起点，但是再往前的站点就不一定。

结论 111：数组 diffdiffdiff 的累加和如果小于 000，一定不能完成旅途。

因为加油与耗油都是 nnn 次，加的总油量比不上消耗的，说明跨越不过全部的坑，完成不了全程。

结论 222：数组 diffdiffdiff 的累加和如果大于等于 000，一定能完成旅途。

假定一共 kkk 个坑，分布在数组的任意位置，共 kkk 个负收益与 n−kn-kn−k 个正收益。如果想要跨越难度最大，就是让所有的坑连在一起，中间不给正收益的机会。但是，只需要让起点定在 最后一个坑的后一个位置，在总累加和大于 000 的前提下，一定有正收益大于负收益，完全能旅行一圈。

思路：从头开始遍历数组，累加每一个位置的 diff[i]diff[i]diff[i]，找到累加和最小的值 minminmin；接着倒序遍历数组，在 minminmin 的基础上继续累加 diff[i]diff[i]diff[i]，找到让累加和为正的位置 idxidxidx，它即为答案。

这种想法就是找到负收益最大的值，为了跨越这个“大坑”，就需要找到一个位置，它的正收益足够抵消这种负面影响，从而跨越这个难题。

为什么两次遍历 方向不同？

规定起点为 000 开始正向累加，负收益的值表示起点为 000 需要弥补的值。所以第二次是倒序遍历，表示让 idxidxidx 作为新的环形起点，将获得的正收益都当作油箱的起始值。

为什么这种贪心思路 正确？

如果答案不存在，累加的 diffdiffdiff 值一定为负，可以直接特判结束；如果答案存在，那么这个最负的位置 minIdxminIdxminIdx，与倒序直到累加为正的位置 idxidxidx 一定满足 minIdx<idxminIdx<idxminIdx<idx。反之，他俩交叉的部分一定有正收益，不能让 minIdxminIdxminIdx 作为最负的位置，所以环形方案可行。题意确保了答案唯一，不会有第二个 idxidxidx 出现。

优点：不需要对下标进行 modmodmod 取余操作；从全局的视角出发，两次遍历的思路比较清晰。

代码如下，已附加注释：

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
       
        int curSum = 0;  // 从0行驶到i后的剩余油量
        int min = Integer.MAX_VALUE;  // 大坑的最负值
        int n = gas.length;
        for(int i = 0; i < n; i++) {
            curSum += (gas[i] - cost[i]);  // 走到第i个位置
            if(curSum < min)  // 找到从0开始最小的值--大坑
                min = curSum;
        }
if(curSum < 0)  // 说明根本就完成不了
            return -1;
        if(min >= 0)  // 说明从0出发是可行的
            return 0;
        for(int i = n - 1; i >= 0; i--) {  // 倒序遍历
            min += (gas[i] - cost[i]);
            if(min >= 0)
                return i;
        }
        return -1;
 }
}

• 时间复杂度： O(n)O(n)O(n)，其中 nnn 为数组 gasgasgas 的长度
• 空间复杂度： O(1)O(1)O(1)，仅用常数个额外变量

新手小白 如有问题 请多指教 求点赞