每日算法练习：LeetCode 134. 加油站 ✅

大家好，我是你们的算法小伙伴。今天我们来练习一道经典的贪心算法题目 ——LeetCode 134. 加油站。这道题考察在环形路径中寻找可行起点，是面试中非常典型的 “贪心选择” 问题。

题目描述

在一条环路上有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 号加油站出发，可获得 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 - 5 = 0，正好回到起点。

示例 2：

输入: gas = [2,3,4], cost = [3,4,3] 输出: -1 解释: 无法绕环路行驶一周。

提示：

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

解题思路

核心前提判断

首先，我们可以快速判断是否存在解：

• 如果总汽油量 < 总消耗量（即sum(gas) < sum(cost)），则一定无法绕一圈，直接返回-1。
• 只有当sum(gas) >= sum(cost)时，才一定存在唯一解。

贪心算法核心思想

我们不需要枚举所有起点，只需要一次遍历即可找到答案：

1. 维护两个变量：
   • currentTank：当前油箱的剩余油量。
   • start：当前候选的起点加油站，初始为0。
2. 遍历每个加油站：
   • 计算当前加油站的净油量diff = gas[i] - cost[i]。
   • currentTank += diff。
   • 如果currentTank < 0，说明从start到i这段路无法走完，起点必须更新为i+1，并重置currentTank = 0。
3. 遍历结束后，start就是唯一的可行起点。

关键逻辑解释

如果从start出发，走到i时油箱变空，说明：

• start到i之间的所有点都不能作为起点（否则会更早油箱为空）。
• 下一个可能的起点只能是i+1。
• 因为总油量足够，所以最终的start一定是正确解。

代码实现

class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { int n = gas.length; int totalGas = 0; int currentTank = 0; int start = 0; for (int i = 0; i < n; i++) { int diff = gas[i] - cost[i]; totalGas += diff; currentTank += diff; // 如果当前油箱油量不足，说明从 start 到 i 走不通，更新起点 if (currentTank < 0) { start = i + 1; currentTank = 0; } } // 总油量 < 总消耗，无解；否则返回 start return totalGas >= 0 ? start : -1; } }

代码详解（结合示例 1 模拟）

示例 1：gas = [1,2,3,4,5],cost = [3,4,5,1,2]

表格

• totalGas = 0 >= 0，存在解。
• 最终start = 3，与示例结果一致。

复杂度分析

• 时间复杂度：O (n)，仅遍历数组一次。
• 空间复杂度：O (1)，仅使用常数级额外空间。

总结

1. 快速判断：先算总油量和总消耗，不足直接返回-1。
2. 贪心选择：一次遍历，遇到油箱不足就更新起点，保证最终找到唯一可行解。
3. 核心逻辑：如果一段路走不通，这段路的所有点都不能作为起点，下一个可能的起点只能是这段路的下一个点。

这道题是贪心算法中 “跳过无效区间” 的经典应用，代码简洁高效，是面试必背模板。

今天的每日算法练习就到这里，我们明天再见！👋