加油站

问题描述

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

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -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 可为起始索引。

分析问题

我们可以把题目的描述抽象成如下的图形结构。其中节点代表每个加油站（节点的值表示可以添加的油量），边的值表示从一个点到另外一个点需要消耗的油量。

这道题最容易想到的就是暴力求解，即遍历所有的站点，以其为出发点，看是否能转一圈再回来。该算法使用了两层for循环，其算法的时间复杂度是O(N^2)。

class Solution:
    def canCompleteCircuit(self, gas, cost):
        #站点个数
        n=len(gas)
        #遍历所有站点，以其为出发点
        for start in range(n):
            j = start
            remain = gas[start]
            #判断当前剩余的油能否到达下一个点
            while remain - cost[j] >= 0:
                #更新剩余的油量
                remain = remain - cost[j] + gas[(j + 1) % n]
                #顺时针移动一位
                j = (j + 1) % n
                #当回到了起始点，代表可以走完一圈，直接返回
                if j == start:
                    return start
        return -1

下面我们来看一下如何进行优化。

优化

在汽车进入加油站站点 i 时，可以加 gas[i] 的油，当离开站点 i ，走到下一个站点 i+1 时， 需要消耗 cost[i] 的油，那么我们可以把站点和与其相连的路看做一个整体来考虑，即 gas[i] - cost[i] 作为经过站点 i 的 油的变化量。如下图所示：

这样，我们就生成了一个环形数组，数组中的第 i 个元素就是 gas[i] - cost[i]。

通过转换后，我们就可以把题目要求变成判断这个环形数组中是否能够找到一个起点start，使得从这个起点开始的累加和一直大于等于 0。

在计算累加和的过程中，如果累加和小于0，就代表以该加油站为起点，是不能走完一圈的，需要换一个加油站作为起点。

决定换哪个加油站为起点呢？这是本题优化的关键所在，也是使用贪心思路求解的关键结论。

这个结论就是：如果选择加油站i作为起点「恰好」无法走到加油站j，那么加油站 i和j中间的任意站点k都不可能作为起点。

下面我们试着来证明一下这个结论的正确性。

假设 sum 记录的是当前油箱的剩余油量，如果从加油站 i （sum=0）出发，走到加油站 j 恰好出现 sum < 0 的情况，也就是说从站点 i 走到 站点k（站点 k 位于 站点 i 和 j 之间）都满足 sum > 0 。

如果把 k 作为起点的话，相当于在站点 k 时， sum=0（出发时，油箱的油量为0），则走到站点 j 时 必然有 sum < 0，也就说明 k 肯定不能是起点。

综上，这个结论就被证明了。

所以，如果我们发现从站点 i 出发无法走到站点 j ，那么站点i以及i, j之间的所有站点都不可能作为起点，从而我们可以减少一些冗余计算了。

具体代码如下所示：

class Solution:
    def canCompleteCircuit(self, gas, cost):
        #站点个数
        n=len(gas)
        #邮箱的剩余量
        sum=0
        #出发位置
        start=0
        while start < n:
            step=0
            while step<n:
                j = (start+step) % n
                # 计算累加和
                sum += gas[j] - cost[j]
                # 如果累加和小于0，
                # 代表以start为起点不能走完一圈
                if sum<0:
                    break

                step=step+1

            if step==n:
                #如果已经走完一圈，直接返回start
                return start
            else:
                #更新start
                start=start+step+1
                sum=0

        return -1