[LeetCode] 134. Gas Station

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

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

Given two integer arrays gas and cost, return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique.

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.

Constraints:
n == gas.length == cost.length
1 <= n <= 105
0 <= gas[i], cost[i] <= 104

加油站。

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/gas-station
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

题意是给一个长度为 n 的环，用数组表示。环上的每一个点都有两个值，一个是当前加油站的油量，一个是开到下一个加油站的耗油量。请找到一个起点能够保证车开完一圈，返回起点的坐标；若找不到这个起点则返回-1。这是一个数学题。这个题涉及一个定理（此处不证明了），如果一个数组的总和非负，那么一定可以找到一个起始位置，从它开始绕数组一圈，累加和一直都是非负的。有了这个定理之后，可以对input做如下判断。

1. 从位置 i 开始直到绕完一圈，如果油箱没空，说明从 i 开始所有的累积都是正的（总的加油量大于耗油量）
2. 如果在位置 j 的时候油箱空了，说明从位置 i 开始是走不完全程的，此时可以从 j + 1 的位置重新开始计算。为什么不考虑从 i + 1 的位置开始重新计算是因为 i 处的油量是正的情况下已经走不完全程了，因为从 i 去到 i + 1也有油耗，如果从 i + 1 开始，更走不完全程了

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        // total记录环内总油量是否足够
        // sum记录当前油箱剩余油量
        int total = 0;
        int sum = 0;
        int start = 0;
        for (int i = 0; i < gas.length; i++) {
            total += gas[i] - cost[i];
            if (sum < 0) {
                sum = gas[i] - cost[i];
                start = i;
            } else {
                sum += gas[i] - cost[i];
            }
        }
        return total < 0 ? -1 : start;
    }
}

JavaScript实现

/**
 * @param {number[]} gas
 * @param {number[]} cost
 * @return {number}
 */
var canCompleteCircuit = function (gas, cost) {
    // corner case
    if (gas.length === 0 || cost.length === 0) return -1;

    // normal case
    let total = 0;
    let sum = 0;
    let start = 0;
    for (let i = 0; i < gas.length; i++) {
        total += (gas[i] - cost[i]);
        if (sum < 0) {
            sum = gas[i] - cost[i];
            start = i;
        } else {
            sum += gas[i] - cost[i];
        }
    }
    return total < 0 ? -1 : start;
};