【LeetCode 134.加油站】贪心算法最优解 超详细解析图文代码证明专栏LeetCode算法题解贪心算法专项难度中等标签#贪心算法 #数组 #环形数组 #LeetCode134一、问题描述在一条环路上有n个加油站其中第i个加油站有汽油gas[i]升。你有一辆油箱容量无限的汽车从第i个加油站开往第i1个加油站需要消耗汽油cost[i]升车辆从选定的加油站出发时油箱为空。给定两个整数数组gas和cost若能按顺序绕环路行驶一周返回出发时加油站的编号若无法完成绕行返回-1。题目保证如果存在解解是唯一的。示例演示示例 1存在有效起点输入输出示例输入: gas [1,2,3,4,5], cost [3,4,5,1,2] 输出: 3推演说明从索引3出发油箱油量全程充足可顺利绕环路一圈返回起点。示例 2无有效起点输入输出示例输入: gas [2,3,4], cost [3,4,3] 输出: -1推演说明总油量小于总消耗无论选择哪个起点都无法完成全程绕行。题目提示与数据范围n gas.length cost.length两个数组长度一致1 n 10^5数据规模大要求算法时间复杂度必须为O(n)0 gas[i], cost[i] 10^4输入保证解唯一无需考虑多解场景二、解题思路深度分析2.1 暴力解法弊端为何不选最直观的思路是枚举每个加油站作为起点模拟绕圈过程判断油量是否全程非负。但这种方法时间复杂度为O(n²)当n10^5时会直接超时无法通过所有测试用例因此必须优化为贪心算法。2.2 贪心算法核心原理附严谨证明贪心算法的核心是抓住全局规律跳过无效起点一次遍历找到答案核心基于两大结论全局可行性判断如果所有加油站的总油量 总消耗无论选哪个起点都无法绕圈直接返回 -1如果总油量 ≥ 总消耗一定存在唯一有效起点。局部贪心跳过规则如果从起点start出发行驶到第i个加油站时油量耗尽油量为负则从 start 到 i 之间的所有加油站都不能作为有效起点直接将新起点设为i1重置当前油箱油量即可。关键证明假设从A出发到B时油量不足那么A到B之间任意一点C出发到B时油量一定更少因为从A到C时油箱已有油量都无法支撑到B空油箱从C出发更不可能因此这段区间可直接跳过无需重复验证。2.3 算法复杂度优势时间复杂度O(n)仅需一次遍历数组无嵌套循环完美适配10^5数据规模空间复杂度O(1)仅使用常数级额外变量无额外空间开销三、完整代码实现标准格式LeetCode 134 贪心解法from typing import List class Solution: def canCompleteCircuit(self, gas: List[int], cost: List[int]) - int: # 统计全局总油量、总消耗用于最终可行性判断 total_gas 0 total_cost 0 # 当前油箱实时油量记录行驶过程中的剩余油量 current_tank 0 # 候选有效起点初始默认从0号加油站出发 start 0 n len(gas) for i in range(n): # 累加全局总量全程只需一次计算 total_gas gas[i] total_cost cost[i] # 更新当前油箱油量加油后减去前往下一站的消耗 current_tank gas[i] - cost[i] # 核心贪心逻辑当前油量不足跳过无效区间更新起点 if current_tank 0: # 起点设为下一个加油站当前区间全部无效 start i 1 # 重置油箱新起点出发时空油箱 current_tank 0 # 全局总油量不足直接返回-1 if total_gas total_cost: return -1 # 题目保证解唯一直接返回候选起点 return start四、代码逐行详解4.1 变量初始化total_gas/total_cost全局统计变量遍历结束后判断是否存在可行解current_tank模拟车辆油箱记录从当前起点出发后的实时油量初始为0start记录最终有效起点初始值为0遍历中动态更新4.2 遍历核心逻辑每遍历一个加油站先累加全局总油量和总消耗无需额外遍历计算单次行驶净油量gas[i] - cost[i]更新当前油箱油量若当前油箱为负说明当前起点到该站区间全部无效更新起点为下一站重置油箱4.3 最终结果判断遍历结束后先判断全局总油量是否足够不足则返回-1足够则直接返回候选起点题目保证唯一。五、测试用例逐行推演5.1 示例1 推演gas [1,2,3,4,5], cost [3,4,5,1,2]i0current_tank 1-3 -2 → 负start1current_tank0i1current_tank 2-4 -2 → 负start2current_tank0i2current_tank 3-5 -2 → 负start3current_tank0i3current_tank 4-1 3 → 正不更新起点i4current_tank 3 (5-2) 6 → 正不更新起点总油量15总消耗15相等返回 start35.2 示例2 推演gas [2,3,4], cost [3,4,3]总油量9总消耗10总油量不足直接返回-1六、边界情况全覆盖处理6.1 单加油站场景n1# 测试用例1油量足够 gas [5], cost [3] → 返回 0 # 测试用例2油量不足 gas [2], cost [3] → 返回 -16.2 油量与消耗完全相等gas [2,2,2], cost [2,2,2] → 返回 06.3 起点在数组末尾gas [3,1,1], cost [1,2,2] → 返回 0七、核心总结与拓展7.1 贪心算法核心要点先判全局再找局部先通过总油量和总消耗判断可行性避免无效遍历跳过无效区间利用贪心规则一次性排除整段无效起点大幅降低时间复杂度空间最优原地遍历无额外数组、哈希表开销空间复杂度O(1)7.2 同类题型拓展本题属于环形数组贪心选择经典题型同类解题思路可迁移至环形路线资源调度问题循环任务最优起点选择连续子数组和的贪心优化问题易错点提醒禁止在生产环境使用暴力解法大数据量下会超时切勿混淆total_gas和current_tank的作用前者判全局后者判局部。原创不易觉得有用的话欢迎点赞、收藏、关注后续持续更新LeetCode高频题解、算法技巧和面试真题解析
【LeetCode 134.加油站】贪心算法最优解 超详细解析｜图文+代码+证明
发布时间：2026/7/18 3:10:59
【LeetCode 134.加油站】贪心算法最优解 超详细解析图文代码证明专栏LeetCode算法题解贪心算法专项难度中等标签#贪心算法 #数组 #环形数组 #LeetCode134一、问题描述在一条环路上有n个加油站其中第i个加油站有汽油gas[i]升。你有一辆油箱容量无限的汽车从第i个加油站开往第i1个加油站需要消耗汽油cost[i]升车辆从选定的加油站出发时油箱为空。给定两个整数数组gas和cost若能按顺序绕环路行驶一周返回出发时加油站的编号若无法完成绕行返回-1。题目保证如果存在解解是唯一的。示例演示示例 1存在有效起点输入输出示例输入: gas [1,2,3,4,5], cost [3,4,5,1,2] 输出: 3推演说明从索引3出发油箱油量全程充足可顺利绕环路一圈返回起点。示例 2无有效起点输入输出示例输入: gas [2,3,4], cost [3,4,3] 输出: -1推演说明总油量小于总消耗无论选择哪个起点都无法完成全程绕行。题目提示与数据范围n gas.length cost.length两个数组长度一致1 n 10^5数据规模大要求算法时间复杂度必须为O(n)0 gas[i], cost[i] 10^4输入保证解唯一无需考虑多解场景二、解题思路深度分析2.1 暴力解法弊端为何不选最直观的思路是枚举每个加油站作为起点模拟绕圈过程判断油量是否全程非负。但这种方法时间复杂度为O(n²)当n10^5时会直接超时无法通过所有测试用例因此必须优化为贪心算法。2.2 贪心算法核心原理附严谨证明贪心算法的核心是抓住全局规律跳过无效起点一次遍历找到答案核心基于两大结论全局可行性判断如果所有加油站的总油量 总消耗无论选哪个起点都无法绕圈直接返回 -1如果总油量 ≥ 总消耗一定存在唯一有效起点。局部贪心跳过规则如果从起点start出发行驶到第i个加油站时油量耗尽油量为负则从 start 到 i 之间的所有加油站都不能作为有效起点直接将新起点设为i1重置当前油箱油量即可。关键证明假设从A出发到B时油量不足那么A到B之间任意一点C出发到B时油量一定更少因为从A到C时油箱已有油量都无法支撑到B空油箱从C出发更不可能因此这段区间可直接跳过无需重复验证。2.3 算法复杂度优势时间复杂度O(n)仅需一次遍历数组无嵌套循环完美适配10^5数据规模空间复杂度O(1)仅使用常数级额外变量无额外空间开销三、完整代码实现标准格式LeetCode 134 贪心解法from typing import List class Solution: def canCompleteCircuit(self, gas: List[int], cost: List[int]) - int: # 统计全局总油量、总消耗用于最终可行性判断 total_gas 0 total_cost 0 # 当前油箱实时油量记录行驶过程中的剩余油量 current_tank 0 # 候选有效起点初始默认从0号加油站出发 start 0 n len(gas) for i in range(n): # 累加全局总量全程只需一次计算 total_gas gas[i] total_cost cost[i] # 更新当前油箱油量加油后减去前往下一站的消耗 current_tank gas[i] - cost[i] # 核心贪心逻辑当前油量不足跳过无效区间更新起点 if current_tank 0: # 起点设为下一个加油站当前区间全部无效 start i 1 # 重置油箱新起点出发时空油箱 current_tank 0 # 全局总油量不足直接返回-1 if total_gas total_cost: return -1 # 题目保证解唯一直接返回候选起点 return start四、代码逐行详解4.1 变量初始化total_gas/total_cost全局统计变量遍历结束后判断是否存在可行解current_tank模拟车辆油箱记录从当前起点出发后的实时油量初始为0start记录最终有效起点初始值为0遍历中动态更新4.2 遍历核心逻辑每遍历一个加油站先累加全局总油量和总消耗无需额外遍历计算单次行驶净油量gas[i] - cost[i]更新当前油箱油量若当前油箱为负说明当前起点到该站区间全部无效更新起点为下一站重置油箱4.3 最终结果判断遍历结束后先判断全局总油量是否足够不足则返回-1足够则直接返回候选起点题目保证唯一。五、测试用例逐行推演5.1 示例1 推演gas [1,2,3,4,5], cost [3,4,5,1,2]i0current_tank 1-3 -2 → 负start1current_tank0i1current_tank 2-4 -2 → 负start2current_tank0i2current_tank 3-5 -2 → 负start3current_tank0i3current_tank 4-1 3 → 正不更新起点i4current_tank 3 (5-2) 6 → 正不更新起点总油量15总消耗15相等返回 start35.2 示例2 推演gas [2,3,4], cost [3,4,3]总油量9总消耗10总油量不足直接返回-1六、边界情况全覆盖处理6.1 单加油站场景n1# 测试用例1油量足够 gas [5], cost [3] → 返回 0 # 测试用例2油量不足 gas [2], cost [3] → 返回 -16.2 油量与消耗完全相等gas [2,2,2], cost [2,2,2] → 返回 06.3 起点在数组末尾gas [3,1,1], cost [1,2,2] → 返回 0七、核心总结与拓展7.1 贪心算法核心要点先判全局再找局部先通过总油量和总消耗判断可行性避免无效遍历跳过无效区间利用贪心规则一次性排除整段无效起点大幅降低时间复杂度空间最优原地遍历无额外数组、哈希表开销空间复杂度O(1)7.2 同类题型拓展本题属于环形数组贪心选择经典题型同类解题思路可迁移至环形路线资源调度问题循环任务最优起点选择连续子数组和的贪心优化问题易错点提醒禁止在生产环境使用暴力解法大数据量下会超时切勿混淆total_gas和current_tank的作用前者判全局后者判局部。原创不易觉得有用的话欢迎点赞、收藏、关注后续持续更新LeetCode高频题解、算法技巧和面试真题解析
