LeetCode-Go 题解134. Gas Station加油站环形路线贪心算法详解【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文以 LeetCode 第 134 题《Gas Station加油站》为核心结合本仓库 LeetCode-Go 中该题的 Go 源码实现 与 单元测试系统讲解环形路线上的油量可行性判定问题如何在 O(n) 时间内确定唯一可行的出发点、如何证明总油量不足则无解以及如何通过一次遍历同时完成可行性判断与起点查找。读完本文你将掌握这类环形可行性 唯一解问题的标准贪心套路并可直接复用仓库中的 Go 实现与测试框架。一、问题定义在一条环形circular路线上分布着n个加油站gas station其中第i个加油站的储油量为gas[i]从第i个加油站行驶到下一个加油站(i1) % n需要消耗cost[i]升汽油汽车油箱容量无限初始油箱为空且只能顺时针行驶要求判断是否存在一个起始加油站编号start使得从该站出发、油箱为空的状态下能够绕整个环一圈并顺利回到出发点若存在则返回该编号题目保证解唯一否则返回-1。输入约束gas.length ncost.length n1 n 10^50 gas[i], cost[i] 10^4。由于n最大可达10^5如果对每个站点都模拟一圈复杂度为 O(n²)在极限数据下不可接受。因此本题考察的核心是能否在线性时间内求解。示例 1存在解Input: gas [1,2,3,4,5], cost [3,4,5,1,2] Output: 3从站点 3 出发的完整模拟过程如下初始 0 升先加本站油再前往下一站当前站加油后油量消耗到下一站时剩余30 4 413下一站 443 5 826下一站 006 1 734下一站 114 2 642下一站 222 3 550恰好回到站点 3最终恰好以 0 升油量回到站点 3因此start 3。示例 2无解Input: gas [2,3,4], cost [3,4,3] Output: -1从站点 0 出发本站加油后 2 升去站点 1 需要 3 升不够从站点 1 出发本站加油后 3 升去站点 2 需要 4 升不够从站点 2 出发本站加油后 4 升去站点 0 消耗 3 升剩 1 升再到站点 1 消耗 3 升不够返回站点 2。三种起点均失败返回-1。二、核心思路一次遍历的贪心判定2.1 两个关键观察观察一总油量是全局可行性的充分必要条件。设totalGas Σgas[i]、totalCost Σcost[i]。若totalGas totalCost说明整个环路的净消耗大于净补给无论从哪一站出发都不可能完成一圈直接返回-1。反过来若totalGas totalCost则一定存在某个可行起点——这是本题解唯一特性背后的数学保证。观察二负油量即断层起点只能向后移动。引入前缀净收益currGas Σ(gas[i] - cost[i])。当扫描到某个位置i时若currGas 0说明从当前的候选起点start到i这一段上任意中间站点作为起点都不可能跨过i这个断点因为无论从start到i之间的哪一站出发其累计剩余只会更少无法抵消i处的亏损。因此候选起点必须重置为i 1并清空累计的currGas重新开始计数。2.2 算法步骤初始化totalGas 0、totalCost 0、currGas 0、start 0遍历i从0到n-1totalGas gas[i]totalCost cost[i]currGas gas[i] - cost[i]若currGas 0令start i 1并将currGas重置为0遍历结束后若totalGas totalCost返回-1否则返回start。时间复杂度 O(n)空间复杂度 O(1)只需常数级额外内存。三、仓库源码实现仓库中本题的完整实现位于 Gas.go与文档思路一一对应package leetcode func canCompleteCircuit(gas []int, cost []int) int { totalGas : 0 totalCost : 0 currGas : 0 start : 0 for i : 0; i len(gas); i { totalGas gas[i] totalCost cost[i] currGas gas[i] - cost[i] if currGas 0 { start i 1 currGas 0 } } if totalGas totalCost { return -1 } return start }代码要点totalGas与totalCost负责最终的全局可行性判定只有两者比较后才决定是否返回-1这保证了currGas中途重置不会影响最终结论start i 1在i为最后一个元素时等于n但由于此时totalGas totalCost必然成立否则提前返回-1start n会被模运算语义自然规约回有效下标范围——实际上当且仅当整体可行时start一定落在[0, n-1]内这一细节也是贪心正确性的体现全程只依赖len(gas)一个长度隐含利用了题目给出的gas.length cost.length约束。四、正确性证明必要性若totalGas totalCost环路整体净消耗大于净补给任何起点都注定失败故返回-1正确充分性若totalGas totalCost把环在可行起点处剪开等价于一段总和非负的序列。贪心扫描不断在currGas 0处重置起点等价于证明从start到n-1的剩余部分总能覆盖前段的全部亏损最终回到原点。这是前缀和思想的直接推论——每次失败段的总和严格为负把所有失败段的总亏损累加后仍然小于总净收益因此最后一个候选起点必然可行唯一性题目已保证若存在解则唯一因此算法无需在多个候选间做比较只需返回最后一次重置后的start。五、测试验证仓库为本题提供了表格驱动table-driven风格的测试位于 Gas_test.gofunc Test_Problem134(t *testing.T) { qs : []question134{ { para134{[]int{1, 2, 3, 4, 5}, []int{3, 4, 5, 1, 2}}, ans134{3}, }, { para134{[]int{2, 3, 4}, []int{3, 4, 3}}, ans134{-1}, }, } ... }测试用例如下输入 gas输入 cost期望输出场景[1,2,3,4,5][3,4,5,1,2]3存在唯一解对应题目示例 1[2,3,4][3,4,3]-1总油量不足无解对应题目示例 2两个用例分别覆盖了可完成与不可完成两条分支恰好命中源码中totalGas totalCost的提前返回路径和正常返回start的路径。在仓库中运行测试本项目根目录的 gotest.sh 展示了全仓库测试的统一下发方式Go 1.10 单次对多包生成合法覆盖率文件go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...若只想运行本题的测试可进入对应目录单独执行cd leetcode/0134.Gas-Station go test -v -run Test_Problem134-run Test_Problem134会精确匹配 Gas_test.go 中的测试函数并打印每个用例的输入与输出。六、变式与延伸推广到非唯一解若题目允许多个解实际中只需返回任一可行起点本算法同样成立因为贪心返回的start一定是可行起点之一判断是否存在解而不求起点只需比较totalGas与totalCost无需维护currGas与start可进一步简化环形数组类问题的通用技巧本题的环形 唯一解结构与经典最大子数组问题Kadane 算法同源均为遇负则重置、局部累积、全局判定的模式在本仓库中类似的前缀和与贪心思路还可参考其他环形类题目例如 918. Maximum-Sum-Circular-Subarray 等。七、小结LeetCode 134 是一道典型的环形可行性 唯一解贪心题核心结论可浓缩为两句话总油量小于总消耗 ⇒ 必然无解返回-1否则第一个能撑过所有负前缀断层的位置即为唯一可行起点一次 O(n) 遍历即可求出。仓库中的 Gas.go 以 4 个变量、单循环实现了上述全部逻辑Gas_test.go 以表格驱动方式覆盖了文档中的两个官方示例可直接复制使用或作为面试速查模板。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考