Medium

题目描述

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

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

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

提示:

  • n == gas.length == cost.length
  • 1 <= n <= 10^5
  • 0 <= gas[i], cost[i] <= 10^4
  • 输入保证答案是唯一的

解题思路

这道题有两种主要解法：暴力解法和贪心算法。

方法一：暴力解法 对于每个可能的起始位置，模拟整个行驶过程，检查是否能够完成环路。时间复杂度为 O(n²)。

方法二：贪心算法（推荐） 这是最优解法，基于以下关键观察：

  1. 如果总油量小于总消耗，必然无解
  2. 如果从位置 i 出发无法到达位置 j，那么从 i 到 j 之间的任何位置出发都无法到达 j
  3. 因此一旦发现当前位置无法继续，就将起始位置设为下一个位置

算法流程：

  • 维护当前油量 currentGas 和总油量差值 totalGas
  • 遍历每个加油站，计算净油量（加油量-消耗量）
  • 如果当前油量不足，说明之前的起始位置不可行，将起始位置更新为下一个位置
  • 最后检查总油量是否非负来判断是否有解

这种方法的时间复杂度为 O(n)，空间复杂度为 O(1)。

代码实现

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

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

public class Solution {
    public int CanCompleteCircuit(int[] gas, int[] cost) {
        int totalGas = 0;
        int currentGas = 0;
        int start = 0;
        
        for (int i = 0; i < gas.Length; i++) {
            int netGas = gas[i] - cost[i];
            totalGas += netGas;
            currentGas += netGas;
            
            if (currentGas < 0) {
                start = i + 1;
                currentGas = 0;
            }
        }
        
        return totalGas >= 0 ? start : -1;
    }
}

var canCompleteCircuit = function(gas, cost) {
    let totalGas = 0;
    let currentGas = 0;
    let start = 0;
    
    for (let i = 0; i < gas.length; i++) {
        const netGas = gas[i] - cost[i];
        totalGas += netGas;
        currentGas += netGas;
        
        if (currentGas < 0) {
            start = i + 1;
            currentGas = 0;
        }
    }
    
    return totalGas >= 0 ? start : -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
贪心算法（推荐）O(n)O(1)
暴力解法O(n²)O(1)

相关题目