题目简述环形路上有“n” 个加油站“gas[i]”第“i” 站可加的油量“cost[i]”从第“i” 站开到第“i1” 站的耗油量最后一站开回第 0 站若能从某站出发顺时针绕行一圈返回该站下标若不能返回“-1”题目保证答案唯一。核心思路贪心算法全局判断如果所有站“gas” 总和 “cost” 总和绝对跑不完直接“-1”。局部贪心从左到右模拟行驶维护当前油箱余量“cur”。一旦“cur 0”说明从当前记录的“start” 出发到不了本站“i”。那么“start” 到“i” 之间的任何一站都不可能作为起点因为油量只会更少直接把起点设为“i1”“cur” 清零重新算。遍历结束后若总油量够则记录的“start” 就是唯一解。 关键性质如果从 A 出发到不了 B那么 A~B 之间任意点出发都到不了 B。Python3 实现LeetCode 可直接提交from typing import Listclass Solution:def canCompleteCircuit(self, gas: List[int], cost: List[int]) - int:total 0 # 全局油差累计cur 0 # 从当前候选起点出发的累计油差start 0 # 候选起点for i in range(len(gas)): diff gas[i] - cost[i] total diff cur diff # 当前累计为负说明从 start 出发到不了 i if cur 0: start i 1 # 起点更新为下一站 cur 0 # 重新累计 # 总油量足够才能跑完否则返回 -1 return start if total 0 else -1复杂度分析维度 复杂度时间 O(n) 只遍历一次空间 O(1) 仅用几个变量为什么贪心是对的一句话理解环形路径上若总油量非负则必然存在唯一一个“最低累计油差点”的下一个位置作为起点。我们上面“cur0” 时不断后移“start”本质上就是在找这个“最低点之后”的位置。对比暴力解法暴力每个站都模拟跑一圈 → O(n²)贪心利用“连续段不可达”性质剪枝 → O(n)面试标准答法 ✅需要我顺便给出带调试打印的版本或者用双指针思路的另一种写法吗
