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

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]。算法步骤设n为站点数量枚举每个可能的起点i从0到n - 1初始化tank gas[i] - cost[i]若tank 0连本站都开不出去直接跳过该起点令j (i 1) % n指向下一站在尚未回到i的循环中在j站加油并减去前往下一站的消耗tank gas[j] - cost[j]若tank 0起点i失败终止本次模拟j前进到(j 1) % n若成功回到i完成一圈返回i若所有起点都失败返回-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 -1public 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(vectorint gas, vectorint 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: Veci32, cost: Veci32) - 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就是合法的起点。算法步骤设n为站点数量初始化双指针start n - 1end 0用start站的净油量初始化tank gas[start] - cost[start]当start end时循环若tank 0start左移一位并把新start站的净油量累加入tank否则把end站的净油量累加入tankend右移一位循环结束后所有站点都已并入区间若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 -1public 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(vectorint gas, vectorint 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: Veci32, cost: Veci32) - 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 -13. 贪心单遍扫描与断点重置直觉先观察一个关键事实若总油量小于总消耗sum(gas) sum(cost)从任何站点出发都不可能跑完全程直接返回-1若总油量足够则必然存在至少一个合法起点在本题的数据保证下答案至多一个。贪心的核心思想是从左到右单遍扫描同时维护当前累计余额total若在某个下标处total变为负数说明从上一个候选起点到该下标之间的任何站点出发都会在同一位置耗尽油量因此这些站点全部可以排除把下一个站点i 1作为新的候选起点并将total清零重计。这条失败区间整体排除的论断是线性解法的理论基石若从i出发到不了j则从i与j之间的任意站点出发也到不了j——因为中间站点到达j时的累计油量严格更少。算法步骤先做全局可行性检查若sum(gas) sum(cost)立即返回-1初始化total 0当前余额与res 0候选起点从0到n - 1遍历所有站点在每个站点i累加净变化total gas[i] - cost[i]若total 0当前候选起点不可行重置total 0把下一站设为新候选res i 1遍历结束后返回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 respublic 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(vectorint gas, vectorint 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: Veci32, cost: Veci32) - 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]手动推演一遍贪心过程下标 igas[i] - cost[i]累计 totaltotal 0?候选 res01 - 3 -2-2是112 - 4 -2-2是223 - 5 -2-2是334 - 1 33否345 - 2 36否3由于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时的累计油量严格更少。只有彻底理解这一原理才能放心使用线性解法这也是面试中考察贪心正确性证明的核心。三种解法对比与选型建议解法核心思想时间复杂度空间复杂度适用场景暴力模拟枚举每个起点并模拟整圈O(n²)O(1)理解问题模型、小规模输入双指针从两端收缩覆盖环形区间O(n)O(1)面试中的进阶加分写法贪心单遍扫描 断点重置O(n)O(1)竞赛与工程首选最简洁三条路线由浅入深暴力法建立模拟一圈的直觉双指针法展示区间合并式思维且 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考