LeetCode笔记——134. 加油站

题目

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

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

如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -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 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。

最近看题解看多了，发现任何题解都不如直接看他的代码来的清晰明了。

// java代码
class Solution {
   
    public int canCompleteCircuit(int[] gas, int[] cost) {
   
        int gasSum = 0;
        int minGas = Integer.MAX_VALUE;
        int minIndex = -1;
        for(int i = 0; i < gas.length; i++) {
   
            int index;
            if(i == 0) {
   
                index = gas.length - 1;
            } else {
   
                index = i - 1;
            }
            gasSum += gas[index] - cost[index];
            if(gasSum < minGas) {
   
                minGas = gasSum;
                minIndex = i;
            }
        }
        return gasSum < 0 ? -1 : minIndex % gas.length;
    }
}

解析

想象你有一辆车（/(ㄒoㄒ)/~~太穷了）🚗，从站0出发，站0给你加了1升的油，从站0到站1的途中，需要消耗3升油，很明显，你从站0开始出发，并不能到达站1。

也可以这么理解，你开到站1后，车里还剩下负2升油。

什么情况代表着我们能够走一圈？

比如我们从站3开始出发，加了4升油，路上消耗了1升，到达站4后还剩下3升油，这就说明我们能够从站3开到站4…

如果我们一路算下去，发现每次到达下一站，车都还有油，一直到我们再次开到站3，这种情况就说明我们能够走一圈。

我们按照这种逻辑做个图，看看从各个站点开始出发，会产生什么样的奇妙效果😀

import numpy as np


import matplotlib.pyplot as plt

plt.figure(1)
x = np.arange(5)

gas = [1, 2, 3, 4, 5]
cost = [-3, -4, -5, -1, -2]
gasSum = 0

plt.grid()

plt.bar(x, gas, color="#08ffc8")

plt.bar(x, cost, color="#ffb6b9")

for i in range(5):
    j = i
    gasSumList = [0] * 5
    gasSum = 0
    while(True):
        dis = (gas[j % len(gas)] + cost[j % len(cost)])
        gasSum += dis
        print("dis = " + str(dis))
        index = (j + 1) % len(gas)
        gasSumList[index] = gasSum
        if j >= len(gas) and (j + 1) % len(gas) == i:
            break
        j = j + 1
    plt.plot(x, gasSumList, '*--', label=str(i))
    for a,b in zip(x,gasSumList):
        plt.text(a, b+0.05, '%.0f' % b, ha='center', va= 'bottom',fontsize=7)
    
plt.legend(loc='upper left')
plt.show()

条形图代表着每个站点的油量（绿色）以及从该站点到下一个站点需要消耗的油量（粉红色）；折线图上的每个点表示着从前一个站点到这个站点车里剩下的油，不同颜色的线对应从不同站点出发的情况。

要看清题目说的，如果题目有解，则该答案为唯一答案

有解，什么时候有解？所有加油站的油一定要比在路上消耗的要多，才可能有解
唯一？如上面那些折线图，只有一条线是完全在x轴上方的，即那条红色的线。这条折线中只要有一个点小于零，就说明这种方式行不通的。比如绿色的那条线，是从站2开始的，根本走不到站3😂。

你有可能注意到了一点，就是这个图好像所有的折现的最低点都是相同的😏？
我们想一想每个点的值是怎么计算的？
$G_{i} = G_{i - 1} + GS_{i - 1} - C_{i - 1}$ (G代表车里的油量，GS代表油站里的油，C代表cost)
从点i-1到点i的过程中，决定这条折线是上升还是下降的，是 $GS_{i - 1} - C_{i - 1}$ 这个值，而对于每个点i - ·来说， $GS_{i - 1} - C_{i - 1}$ 都是固定的，所以从i - 1到点i这条线是升是降，都是固定的，无论你从哪个点开始开车🚗，i - 1到i该升就是升，该降就是降。

如果只有一个解，那么这一个解构成的折线一定整体都在x轴上方，即最小值>=0；并且通过上面的定性分析，所有的折线的最小值应该会出现在同一个位置。

所以我们要做的
第一件事就是：判断是否有解，对于本题来说，所有的油为15升，所有的花费为15升，所以有解；
第二件事：找到最低点，这里我们采取哪个点作为起始点都行，用最后一个作为起始点会简化计算。
比如我们从站4开始，下一站是站0，那么到达站0的时候车里还剩下3升油

从站0到站1，还剩下3 + 1 - 3 = 1升
从站1到站2，还剩下1 + 2 - 4 = -3升
从站2到站3，还剩下-3 + 3 - 5 = -5升
从站3到站4，还剩下-5 + 4 - 1 = -2升

很明显最低的是站3，那么我们可以知道，从站3出发，最后一定能够回到站3

直接看红色的那条线就行了。