134 Gas Station 加油站

Description:
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 in the clockwise direction, otherwise return -1.

Note:

If there exists a solution, it is guaranteed to be unique.
Both input arrays are non-empty and have the same length.
Each element in the input arrays is a non-negative integer.

Example:

Example 1:

Input:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]

Output: 3

Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

Example 2:

Input:
gas = [2,3,4]
cost = [3,4,3]

Output: -1

Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.

題目描述:
在一條環(huán)路上有 N 個(gè)加油站，其中第 i 個(gè)加油站有汽油 gas[i] 升。

你有一輛油箱容量無(wú)限的的汽車，從第 i 個(gè)加油站開(kāi)往第 i+1 個(gè)加油站需要消耗汽油 cost[i] 升。你從其中的一個(gè)加油站出發(fā)，開(kāi)始時(shí)油箱為空。

如果你可以繞環(huán)路行駛一周，則返回出發(fā)時(shí)加油站的編號(hào)，否則返回 -1。

說(shuō)明：

如果題目有解，該答案即為唯一答案。
輸入數(shù)組均為非空數(shù)組，且長(zhǎng)度相同。
輸入數(shù)組中的元素均為非負(fù)數(shù)。

示例 :

示例 1:

輸入:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]

輸出: 3

解釋:
從 3 號(hào)加油站(索引為 3 處)出發(fā)，可獲得 4 升汽油。此時(shí)油箱有 = 0 + 4 = 4 升汽油
開(kāi)往 4 號(hào)加油站，此時(shí)油箱有 4 - 1 + 5 = 8 升汽油
開(kāi)往 0 號(hào)加油站，此時(shí)油箱有 8 - 2 + 1 = 7 升汽油
開(kāi)往 1 號(hào)加油站，此時(shí)油箱有 7 - 3 + 2 = 6 升汽油
開(kāi)往 2 號(hào)加油站，此時(shí)油箱有 6 - 4 + 3 = 5 升汽油
開(kāi)往 3 號(hào)加油站，你需要消耗 5 升汽油，正好足夠你返回到 3 號(hào)加油站。
因此，3 可為起始索引。

示例 2:

輸入:
gas = [2,3,4]
cost = [3,4,3]

輸出: -1

解釋:
你不能從 0 號(hào)或 1 號(hào)加油站出發(fā)，因?yàn)闆](méi)有足夠的汽油可以讓你行駛到下一個(gè)加油站。
我們從 2 號(hào)加油站出發(fā)，可以獲得 4 升汽油。 此時(shí)油箱有 = 0 + 4 = 4 升汽油
開(kāi)往 0 號(hào)加油站，此時(shí)油箱有 4 - 3 + 2 = 3 升汽油
開(kāi)往 1 號(hào)加油站，此時(shí)油箱有 3 - 3 + 3 = 3 升汽油
你無(wú)法返回 2 號(hào)加油站，因?yàn)榉党绦枰?4 升汽油，但是你的油箱只有 3 升汽油。
因此，無(wú)論怎樣，你都不可能繞環(huán)路行駛一周。

思路:

1. 對(duì)每一個(gè)點(diǎn)進(jìn)行測(cè)試, 看能否按照規(guī)則跑一圈
   時(shí)間復(fù)雜度O(n ^ 2), 空間復(fù)雜度O(1)
2. 首先, 每個(gè)站點(diǎn)的富余油量應(yīng)該是 gas[i] - cost[i], 表示經(jīng)過(guò)該點(diǎn)可以額外獲得多少汽油, 負(fù)值表示消耗量
   如果 sum(gas[i] - cost[i]) < 0則油量不夠, 一定不能跑一圈
   用 rest記錄富余油量, run記錄已經(jīng)經(jīng)過(guò)的點(diǎn)需要的油量, 初始化均為 0
   比如
   gas = [1,2,3,4,5]
   cost = [3,4,5,1,2]
   rest = [-2, -2, -2, 3, 3]
   i = 0, rest = -2, run = 0, rest < run
   rest < run表示剩余的油量不足以支撐汽車跑過(guò)這個(gè)點(diǎn)
   令 run = rest, 重新從下一個(gè)開(kāi)始計(jì)算, 這個(gè)時(shí)候 run表示從該點(diǎn)出發(fā)如果能覆蓋前面的點(diǎn)需要的油量
   最后檢查 rest如果不為負(fù), 說(shuō)明可以跑一圈
   時(shí)間復(fù)雜度O(n), 空間復(fù)雜度O(1)

代碼:
C++:

class Solution 
{
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) 
    {
        int result = 0, rest = 0, run = 0;
        for (int i = 0; i < gas.size(); i++) 
        {
            rest += gas[i] - cost[i];
            if (rest < run) 
            {
                run = rest;
                result = i + 1;
            }
        }
        return rest < 0 ? -1 : result;
    }
};

Java:

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int result = 0, rest = 0, run = 0;
        for (int i = 0; i < gas.length; i++) {
            rest += gas[i] - cost[i];
            if (rest < run) {
                run = rest;
                result = i + 1;
            }
        }
        return rest < 0 ? -1 : result;
    }
}

Python:

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        rest, run, result = 0, 0, 0
        for i in range(len(gas)):
            rest += gas[i] - cost[i]
            if rest < run:
                run = rest
                result = i + 1
        return -1 if rest < 0 else result