题目描述：

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

Note:

The solution is guaranteed to be unique.

题目大意：

有N个加油站围成一个环形，其中第i个加油站的储油量为gas[i]。

你有一辆油箱无限大的汽车，从第i个加油站出发到第i+1个加油站的耗油量为cost[i]。你从某一个加油站开始旅行，初始油箱为空。

如果从某一个加油站出发可以走完一圈，返回该加油站的下标，否则返回-1。

注意：

可行解确保是唯一的。

解题思路：

贪心算法（Greedy Algorithm)

分析题目可以得到两个隐含的结论：

结论1：若从加油站A出发，恰好无法到达加油站C（只能到达C的前一站）。则A与C之间的任何一个加油站B均无法到达C。

结论1的证明：反证法

假设从加油站A出发恰好无法到达加油站C，但是A与C之间存在加油站B，从B出发可以到达C。

而又因为从A出发可以到达B，所以A到B的油量收益（储油量 - 耗油量）为正值，进而可以到达C。

推出矛盾，假设不成立。

结论2：若储油量总和sum(gas) >= 耗油量总和sum(cost)，则问题一定有解。

结论2的证明：反证法

假设sum(gas) >= sum(cost)时，从环形内任意加油站出发，均无法走完一圈。

则从任意加油站A出发绕行一圈返回A之前，油量增益减为负值，假设恰好无法到达加油站B。

亦即：sum(gas[A~B]) < sum(cost[A~B])

而又因为加油站B出发绕行一圈返回B之前，油量增益减为负值，假设恰好无法到达加油站C。

亦即：sum(gas[B~C]) < sum(cost[B~C])

以此类推，最终将进入循环，假设循环的起点为P，中间点为M1, M2 ... Mk

则有：

储油量总和：sum(gas[P~M1] + ... + gas[Mk ~ P]) = c * sum(gas)

耗油量总和：sum(cost[P~M1] + ... + cost[Mk ~ P]) = c * sum(cost)

亦即：

c * sum(gas) < c * sum(cost) 等价于 sum(gas) < sum(cost)

推出矛盾，假设不成立。

Python代码：

class Solution:
    # @param {integer[]} gas
    # @param {integer[]} cost
    # @return {integer}
    def canCompleteCircuit(self, gas, cost):
        start = sums = 0
        for x in range(len(gas)):
            sums += gas[x] - cost[x]
            if sums < 0:
                start, sums = x + 1, 0
        return start if sum(gas) >= sum(cost) else -1

 

本文链接：http://bookshadow.com/weblog/2015/08/06/leetcode-gas-station/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码