企业官网建设流程全解析

LeetCode 134 加油站（Gas Station）解法全解：从暴力模拟到双指针与贪心的线性最优解

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本篇指南围绕 LeetCode 134「加油站（Gas Station）」展开，系统讲解在环形路线上寻找可行起点的三类解法：暴力模拟、双指针收缩与贪心单遍扫描，并逐一给出多语言实现、复杂度分析与易错点。读者学完后，将掌握环形数组遍历、区间合并式双指针以及"断点重置"贪心思想的通用推导方法，能够独立写出并论证 O(n) 时间、O(1) 空间的线性解法。文中所有代码均与仓库 articles/gas-station.md 及各语言 0134-gas-station 实现一一对应，可直接对照运行验证。

问题背景与前置知识

在n个加油站组成的环形路线上，gas[i]表示第i个加油站可加的油量，cost[i]表示从第i个站开到下一个站消耗的油量。汽车油箱初始为空，需要找出一个起始站点下标，使得从它出发绕完整圈后油箱始终不为负；若不存在则返回-1。

在动手解题前，需要具备以下基础：

• 贪心算法（Greedy Algorithms）：理解局部决策如何推导出全局可行性，这是线性解法的核心；
• 数组遍历（Array Traversal）：在遍历中维护累计值（running total）；
• 双指针（Two Pointers）：从两端相向收缩，逐步排除不可能作为起点的候选；
• 环形数组处理（Circular Array Handling）：用模运算(j + 1) % n实现下标回绕。

仓库对该题的提示文档 hints/gas-station.md 给出了同样的目标指引：应当追求O(n) 时间、O(1) 空间的解法，并建议从暴力模拟出发，再过渡到贪心思路。

1. 暴力模拟：最直接的思路

直觉

我们的目标是找到一个起始站点i，使得从它出发恰好绕完整圈，且油箱在任何时刻不为负。最直接的想法是：

• 尝试从每一个站点i出发；
• 模拟绕圈过程；
• 一旦油箱变为负数，该起点失败；
• 若成功回到i，则i就是合法答案。

在每个站点j处，油箱的变化遵循固定的先后顺序：先在j站加油得到gas[j]，再消耗cost[j]开往下一站(j + 1) % n，因此净变化量为gas[j] - cost[j]。

算法步骤

1. 设n为站点数量；
2. 枚举每个可能的起点i，从0到n - 1：
   • 初始化tank = gas[i] - cost[i]；
   • 若tank < 0，连本站都开不出去，直接跳过该起点；
3. 令j = (i + 1) % n指向下一站；
4. 在尚未回到i的循环中：
   • 在j站加油并减去前往下一站的消耗：tank += gas[j] - cost[j]；
   • 若tank < 0，起点i失败，终止本次模拟；
   • j前进到(j + 1) % n；
5. 若成功回到i（完成一圈），返回i；
6. 若所有起点都失败，返回-1。

多语言实现

class Solution: def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int: n = len(gas) for i in range(n): tank = gas[i] - cost[i] if tank < 0: continue j = (i + 1) % n while j != i: tank += gas[j] tank -= cost[j] if tank < 0: break j += 1 j %= n if j == i: return i return -1

public class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { int n = gas.length; for (int i = 0; i < n; i++) { int tank = gas[i] - cost[i]; if (tank < 0) continue; int j = (i + 1) % n; while (j != i) { tank += gas[j] - cost[j]; if (tank < 0) break; j = (j + 1) % n; } if (j == i) return i; } return -1; } }

class Solution { public: int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { int n = gas.size(); for (int i = 0; i < n; i++) { int tank = gas[i] - cost[i]; if (tank < 0) continue; int j = (i + 1) % n; while (j != i) { tank += gas[j] - cost[j]; if (tank < 0) break; j = (j + 1) % n; } if (j == i) return i; } return -1; } };

class Solution { /** * @param {number[]} gas * @param {number[]} cost * @return {number} */ canCompleteCircuit(gas, cost) { const n = gas.length; for (let i = 0; i < n; i++) { let tank = gas[i] - cost[i]; if (tank < 0) continue; let j = (i + 1) % n; while (j !== i) { tank += gas[j] - cost[j]; if (tank < 0) break; j = (j + 1) % n; } if (j === i) return i; } return -1; } }

public class Solution { public int CanCompleteCircuit(int[] gas, int[] cost) { int n = gas.Length; for (int i = 0; i < n; i++) { int tank = gas[i] - cost[i]; if (tank < 0) continue; int j = (i + 1) % n; while (j != i) { tank += gas[j] - cost[j]; if (tank < 0) break; j = (j + 1) % n; } if (j == i) return i; } return -1; } }

func canCompleteCircuit(gas []int, cost []int) int { n := len(gas) for i := 0; i < n; i++ { tank := gas[i] - cost[i] if tank < 0 { continue } j := (i + 1) % n for j != i { tank += gas[j] tank -= cost[j] if tank < 0 { break } j = (j + 1) % n } if j == i { return i } } return -1 }

class Solution { fun canCompleteCircuit(gas: IntArray, cost: IntArray): Int { val n = gas.size for (i in 0 until n) { var tank = gas[i] - cost[i] if (tank < 0) { continue } var j = (i + 1) % n while (j != i) { tank += gas[j] tank -= cost[j] if (tank < 0) { break } j = (j + 1) % n } if (j == i) { return i } } return -1 } }

class Solution { func canCompleteCircuit(_ gas: [Int], _ cost: [Int]) -> Int { let n = gas.count for i in 0..<n { var tank = gas[i] - cost[i] if tank < 0 { continue } var j = (i + 1) % n while j != i { tank += gas[j] tank -= cost[j] if tank < 0 { break } j += 1 j %= n } if j == i { return i } } return -1 } }

impl Solution { pub fn can_complete_circuit(gas: Vec<i32>, cost: Vec<i32>) -> i32 { let n = gas.len(); for i in 0..n { let mut tank = gas[i] - cost[i]; if tank < 0 { continue; } let mut j = (i + 1) % n; while j != i { tank += gas[j] - cost[j]; if tank < 0 { break; } j = (j + 1) % n; } if j == i { return i as i32; } } -1 } }

复杂度分析

• 时间复杂度：$O(n^2)$ —— 最坏情况下每个起点都要模拟几乎整圈；
• 空间复杂度：$O(1)$ —— 只使用常数个临时变量。

暴力法正确但低效，适合作为理解问题模型的起点，无法通过大数据量测试。

2. 双指针：从两端收缩覆盖环形区间

直觉

暴力法把每个站点都当作候选起点重跑一遍，做了大量重复工作。双指针法把环形路线想象成一条待"覆盖"的区间，用两个指针从两端同时逼近：

• start从数组末尾向前移动（向左扩展）；
• end从数组开头向后移动（向右扩展）；
• tank维护当前已覆盖区间的净油量余额。

每一步根据当前tank决定扩展哪一侧：

• 若tank < 0，说明当前区间入不敷出，必须向左移动start纳入更多站点的油量；
• 若tank >= 0，可以安全地向右扩展，纳入end指向的站点。

如此反复，直到start与end相遇，整个环被完整覆盖。若最终tank >= 0，则start就是合法的起点。

算法步骤

1. 设n为站点数量；
2. 初始化双指针：start = n - 1，end = 0；
3. 用start站的净油量初始化tank = gas[start] - cost[start]；
4. 当start > end时循环：
   • 若tank < 0：start左移一位，并把新start站的净油量累加入tank；
   • 否则：把end站的净油量累加入tank，end右移一位；
5. 循环结束后所有站点都已并入区间；
6. 若tank >= 0，返回start；否则返回-1。

多语言实现

class Solution: def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int: n = len(gas) start, end = n - 1, 0 tank = gas[start] - cost[start] while start > end: if tank < 0: start -= 1 tank += gas[start] - cost[start] else: tank += gas[end] - cost[end] end += 1 return start if tank >= 0 else -1

public class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { int n = gas.length; int start = n - 1, end = 0; int tank = gas[start] - cost[start]; while (start > end) { if (tank < 0) { start--; tank += gas[start] - cost[start]; } else { tank += gas[end] - cost[end]; end++; } } return tank >= 0 ? start : -1; } }

class Solution { public: int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { int n = gas.size(); int start = n - 1, end = 0; int tank = gas[start] - cost[start]; while (start > end) { if (tank < 0) { start--; tank += gas[start] - cost[start]; } else { tank += gas[end] - cost[end]; end++; } } return tank >= 0 ? start : -1; } };

class Solution { /** * @param {number[]} gas * @param {number[]} cost * @return {number} */ canCompleteCircuit(gas, cost) { const n = gas.length; let start = n - 1, end = 0; let tank = gas[start] - cost[start]; while (start > end) { if (tank < 0) { start--; tank += gas[start] - cost[start]; } else { tank += gas[end] - cost[end]; end++; } } return tank >= 0 ? start : -1; } }

public class Solution { public int CanCompleteCircuit(int[] gas, int[] cost) { int n = gas.Length; int start = n - 1, end = 0; int tank = gas[start] - cost[start]; while (start > end) { if (tank < 0) { start--; tank += gas[start] - cost[start]; } else { tank += gas[end] - cost[end]; end++; } } return tank >= 0 ? start : -1; } }

func canCompleteCircuit(gas []int, cost []int) int { n := len(gas) start, end := n-1, 0 tank := gas[start] - cost[start] for start > end { if tank < 0 { start-- tank += gas[start] - cost[start] } else { tank += gas[end] - cost[end] end++ } } if tank >= 0 { return start } return -1 }

class Solution { fun canCompleteCircuit(gas: IntArray, cost: IntArray): Int { val n = gas.size var start = n - 1 var end = 0 var tank = gas[start] - cost[start] while (start > end) { if (tank < 0) { start-- tank += gas[start] - cost[start] } else { tank += gas[end] - cost[end] end++ } } return if (tank >= 0) start else -1 } }

class Solution { func canCompleteCircuit(_ gas: [Int], _ cost: [Int]) -> Int { let n = gas.count var start = n - 1 var end = 0 var tank = gas[start] - cost[start] while start > end { if tank < 0 { start -= 1 tank += gas[start] - cost[start] } else { tank += gas[end] - cost[end] end += 1 } } return tank >= 0 ? start : -1 } }

impl Solution { pub fn can_complete_circuit(gas: Vec<i32>, cost: Vec<i32>) -> i32 { let n = gas.len(); let mut start = n - 1; let mut end = 0; let mut tank = gas[start] - cost[start]; while start > end { if tank < 0 { start -= 1; tank += gas[start] - cost[start]; } else { tank += gas[end] - cost[end]; end += 1; } } if tank >= 0 { start as i32 } else { -1 } } }

复杂度分析

• 时间复杂度：$O(n)$ —— 两个指针合计至多移动n次；
• 空间复杂度：$O(1)$。

仓库实现对照

仓库 python/0134-gas-station.py 采用了同源但边界写法不同的双指针变体：使用while start >= end作为外层循环，并用内层while total < 0 and start >= end连续回退start直到余额非负，随后判断start == end返回。两种写法在数学上等价，核心都是"余额不足向左扩展、余额充足向右扩展"，可以作为对照阅读：

class Solution: def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int: start, end = len(gas) - 1, 0 total = gas[start] - cost[start] while start >= end: while total < 0 and start >= end: start -= 1 total += gas[start] - cost[start] if start == end: return start total += gas[end] - cost[end] end += 1 return -1

3. 贪心：单遍扫描与断点重置

直觉

先观察一个关键事实：

• 若总油量小于总消耗（sum(gas) < sum(cost)），从任何站点出发都不可能跑完全程，直接返回-1；
• 若总油量足够，则必然存在至少一个合法起点；在本题的数据保证下，答案至多一个。

贪心的核心思想是从左到右单遍扫描，同时维护当前累计余额total：

• 若在某个下标处total变为负数，说明从上一个候选起点到该下标之间的任何站点出发，都会在同一位置耗尽油量；
• 因此这些站点全部可以排除，把下一个站点i + 1作为新的候选起点，并将total清零重计。

这条"失败区间整体排除"的论断是线性解法的理论基石：若从i出发到不了j，则从i与j之间的任意站点出发也到不了j——因为中间站点到达j时的累计油量严格更少。

算法步骤

1. 先做全局可行性检查：若sum(gas) < sum(cost)，立即返回-1；
2. 初始化total = 0（当前余额）与res = 0（候选起点）；
3. 从0到n - 1遍历所有站点；
4. 在每个站点i累加净变化：total += gas[i] - cost[i]；
5. 若total < 0：
   • 当前候选起点不可行，重置total = 0；
   • 把下一站设为新候选：res = i + 1；
6. 遍历结束后，返回res。

多语言实现

class Solution: def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int: if sum(gas) < sum(cost): return -1 total = 0 res = 0 for i in range(len(gas)): total += (gas[i] - cost[i]) if total < 0: total = 0 res = i + 1 return res

public class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { if (Arrays.stream(gas).sum() < Arrays.stream(cost).sum()) { return -1; } int total = 0; int res = 0; for (int i = 0; i < gas.length; i++) { total += (gas[i] - cost[i]); if (total < 0) { total = 0; res = i + 1; } } return res; } }

class Solution { public: int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { if (accumulate(gas.begin(), gas.end(), 0) < accumulate(cost.begin(), cost.end(), 0)) { return -1; } int total = 0; int res = 0; for (int i = 0; i < gas.size(); i++) { total += (gas[i] - cost[i]); if (total < 0) { total = 0; res = i + 1; } } return res; } };

class Solution { /** * @param {number[]} gas * @param {number[]} cost * @return {number} */ canCompleteCircuit(gas, cost) { if ( gas.reduce((acc, val) => acc + val, 0) < cost.reduce((acc, val) => acc + val, 0) ) { return -1; } let total = 0; let res = 0; for (let i = 0; i < gas.length; i++) { total += gas[i] - cost[i]; if (total < 0) { total = 0; res = i + 1; } } return res; } }

public class Solution { public int CanCompleteCircuit(int[] gas, int[] cost) { if (gas.Sum() < cost.Sum()) { return -1; } int total = 0; int res = 0; for (int i = 0; i < gas.Length; i++) { total += (gas[i] - cost[i]); if (total < 0) { total = 0; res = i + 1; } } return res; } }

func canCompleteCircuit(gas []int, cost []int) int { if sum(gas) < sum(cost) { return -1 } total := 0 res := 0 for i := range gas { total += gas[i] - cost[i] if total < 0 { total = 0 res = i + 1 } } return res } func sum(nums []int) int { var total int for _, num := range nums { total += num } return total }

class Solution { fun canCompleteCircuit(gas: IntArray, cost: IntArray): Int { if (gas.sum() < cost.sum()) { return -1 } var total = 0 var res = 0 for (i in gas.indices) { total += gas[i] - cost[i] if (total < 0) { total = 0 res = i + 1 } } return res } }

class Solution { func canCompleteCircuit(_ gas: [Int], _ cost: [Int]) -> Int { if gas.reduce(0, +) < cost.reduce(0, +) { return -1 } var total = 0 var res = 0 for i in 0..<gas.count { total += (gas[i] - cost[i]) if total < 0 { total = 0 res = i + 1 } } return res } }

impl Solution { pub fn can_complete_circuit(gas: Vec<i32>, cost: Vec<i32>) -> i32 { if gas.iter().sum::<i32>() < cost.iter().sum::<i32>() { return -1; } let mut total = 0; let mut res = 0; for i in 0..gas.len() { total += gas[i] - cost[i]; if total < 0 { total = 0; res = i as i32 + 1; } } res } }

复杂度分析

• 时间复杂度：$O(n)$ —— 单遍扫描 + 一次全局求和；
• 空间复杂度：$O(1)$。

仓库实现对照与运行示例

仓库内绝大多数语言实现都采用贪心单遍写法，可作为交叉验证的"参考答案"：

• cpp/0134-gas-station.cpp：注释中给出了典型用例gas = [1,2,3,4,5]、cost = [3,4,5,1,2]，答案为下标3（第 4 个加油站），其油箱轨迹为4, 8, 7, 6, 5，全程非负；
• java/0134-gas-station.java、go/0134-gas-station.go、c/0134-gas-station.c、ruby/0134-gas-station.rb、typescript/0134-gas-station.ts、kotlin/0134-gas-station.kt 均为"先判总和、再单遍重置"的同一套路。

以官方示例gas = [1,2,3,4,5]、cost = [3,4,5,1,2]手动推演一遍贪心过程：

由于sum(gas) = 15 >= sum(cost) = 15，最终返回res = 3，与 C++ 注释中的结论一致。同时注意：即使候选起点一度被推到3，最终还要依赖全局油量检查来兜底保证res合法。

常见陷阱与易错点

忘记先做"总油量 vs 总消耗"的全局检查

贪心解法建立在"总油量充足则必有解"的前提上。若跳过sum(gas) >= sum(cost)的检查，在无解用例上贪心扫描仍会返回一个res下标，造成假阳性。因此必须在进入贪心逻辑前先做全局判断，这也是 hints/gas-station.md 第二条提示明确强调的要点。

重置起点时错用i而不是i + 1

当累计余额在i处变为负数时，新候选起点应为i + 1。常见错误是写成res = i——但这恰恰是我们刚刚证明会失败的位置。另外当i + 1 == n时看似没有候选起点，实际由总油量检查兜底，无需额外处理。

不理解"失败区间可整体跳过"的原理

贪心之所以是 O(n)，关键在于失败区间可以整段排除：若从i出发无法到达j，那么从(i, j)之间的任意站点出发同样无法到达j，因为它们在到达j时的累计油量严格更少。只有彻底理解这一原理，才能放心使用线性解法，这也是面试中考察贪心正确性证明的核心。

三种解法对比与选型建议

三条路线由浅入深：暴力法建立"模拟一圈"的直觉；双指针法展示区间合并式思维，且 python/0134-gas-station.py 提供了可直接运行的双指针变体；贪心法则把同类问题（环形可行性判定）收敛到"全局可行性检查 + 前缀断点重置"这一可迁移的通用模式，适用于其他环形数组与资源分配类题目。建议在练习时用gas = [1,2,3,4,5]、cost = [3,4,5,1,2]与gas = [2,3,4]、cost = [3,4,3]（无解返回 -1）两组用例分别验证三种实现，确认输出一致后再上机提交。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode