134.Gas Station¶

134.Gas Station¶

Tags: Medium Greedy

Links: https://leetcode.com/problems/gas-station/

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 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.

Answer:

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int index = -1;
        int n = gas.size();

        for (int i = 0; i < n; ++i){
            if (gas[i] >= cost[i]){
                int tank = 0;
                tank = tank + gas[i] - cost[i];
                index = (i + 1) % n;

                while(tank >= 0 && index != i){
                    tank = tank + gas[index] - cost[index];
                    index = (index + 1) % n;
                }

                if(index == i && tank >= 0)
                    break;
            }

            index = -1;
        }

        return index;
    }
};

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int total = 0, j = -1;

        for (int i = 0, sum = 0; i < gas.size(); ++i){
            sum += gas[i] - cost[i];
            total += gas[i] - cost[i];

            if(sum < 0){
                j = i;
                sum = 0;
            }
        }

        return total >= 0 ? j+1 : -1;
    }
};

多一些思考：题目里明确指出如果路径存在，则方法唯一，如果路径不唯一呢，会有多少种解法？如何判断路径唯一不唯一？比如

gas = [2 2 2 2]
cost = [1 1 1 1]

则从任意一个点出发都可以回到起始点。

思路分析：

存在性：如果 $\sum gas < \sum cost$ ，那么不可能回到起点。不妨假设存在这样一个起始点，使车可以绕整个数组一圈。绕一圈的结果就是把gas的所有项相加，即 $\sum gas$ ，那么需要消耗的油量就是。 $\sum gas$ 如果存在此起始点，则 $\sum gas \geq \sum cost$ ，与假设矛盾了。如果 $\sum gas \geq \sum cost$ ，则存在一个起点使之绕一圈回到起点。原命题可以等价为：存在一个数组元素，以它为起始点出发，绕数组一圈，能保证累加和一直是出于非负状态。不妨假设对于任意一个起始点，绕数组一圈，在累加过程中会出现负数状态。出现累加和为负，也就是说 $\sum gas < \sum cost$ ，显然和条件 $\sum gas \geq \sum cost$ 矛盾，所以必存在一个起始点。

唯一性：没有固定方法，只能统计找到的求解方案。

如何寻找起始点：两个数组对应项作差，即gas[i] - cost[i]，得到一个新数组，设新数组为 $s = [a_0, a_1, a_2 \cdots a_{n - 1}]$ 。从第一个非负项开始检查，如果某一项 $a_i$ 出现sum < 0，那么从 $a_{i + 1}$ 开始继续寻找。显然在前i - 1项其总和非负，到了 $a_{i}$ 为负值，说明 $a_i$ 并为负值，倘若从刚才的第一个非负项的后一项开始检查，则到 $a_i$ 的总和为sum减去一个非负数，所以仍然小于0。