Gas Station - LeetCode

https://leetcode.com/problems/gas-station/?envType=study-plan-v2&envId=top-interview-150

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
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n = len(gas)
        for i in range(n):
            if cost[i] > gas[i] or gas[i] == 0:
                continue
            else:
                cnt = 0
                tank = gas[i]
                for j in range(n):
                    tank -= cost[(j + i) % n]
                    if tank >= 0:
                        tank += gas[(j + i + 1) % n]
                        cnt += 1
                    else:
                        break
                    if cnt == n:
                        return i
        
        return -1

这种方法的时间复杂度是O(n^2)，在最坏的情况下，可能会很慢。

为了提高这个算法的效率，我们可以采用一种贪婪的策略。

考虑下面的观察结果：

  1. 如果从一个加油站不能到达另一个加油站，那么这两个加油站之间的任何一个加油站都不能到达第二个加油站。
  2. 如果总的油量 >= 总的花费，那么环路一定可以完成。

基于以上观察，我们可以实现一个O(n)的解法。

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        # 初始化变量
        total_tank, curr_tank = 0, 0
        starting_station = 0
        
        # 遍历每一个加油站
        for i in range(len(gas)):
            total_tank += gas[i] - cost[i]
            curr_tank += gas[i] - cost[i]
            
            # 如果当前油箱为空，设置下一个加油站为起始站，并清空当前油箱
            if curr_tank < 0:
                starting_station = i + 1
                curr_tank = 0
        
        # 如果总的油量 >= 总的花费，返回起始站，否则返回-1
        return starting_station if total_tank >= 0 else -1

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int current_tank = 0;
        int total_tank = 0;
        int start_station = 0;

        for (int i = 0; i < gas.length; i++) {
            current_tank += gas[i] - cost[i];
            total_tank += gas[i] - cost[i];
            if (current_tank < 0){
                current_tank = 0;
                start_station = i + 1;
            }
        }
        if (total_tank >= 0){
            return start_station;
        }else{
            return -1;
        }
    }
}

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int current_tank = 0;
    int total_tank = 0;
    int station = 0;

    for (int i = 0; i < gas.size(); ++i) {
        current_tank += gas[i] - cost[i];
        total_tank += gas[i] - cost[i];
        if (current_tank < 0){
            current_tank = 0;
            station = i + 1;
        }
    }
    return total_tank >= 0 ? station : -1;
    }
};