当前位置：首页 > news >正文

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

news 2026/5/12 18:34:40

大家好，我是你们的算法小伙伴。今天我们来练习一道经典的贪心算法题目 ——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)时，才一定存在唯一解。

贪心算法核心思想

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

维护两个变量：
- currentTank：当前油箱的剩余油量。
- start：当前候选的起点加油站，初始为0。
遍历每个加油站：
- 计算当前加油站的净油量diff = gas[i] - cost[i]。
- currentTank += diff。
- 如果currentTank < 0，说明从start到i这段路无法走完，起点必须更新为i+1，并重置currentTank = 0。
遍历结束后，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; } }