LeetCode 134 · 加油站：一次遍历，油箱亏了就换起点

这道题和 LeetCode 55跳跃游戏有异曲同工之妙——都是维护一个连续区间的状态状态崩了就从下一个位置重新开始。核心思路就一句话如果从某个加油站出发中途油不够了那从这中间的任何一站出发都不行直接跳到下一站重新开始。题目长什么样环形路上有n个加油站gas[i]是第i站能加的油量cost[i]是从第i站到下一站的耗油量。找一个出发点使得能绕一圈回到起点。输入gas [1,2,3,4,5], cost [3,4,5,1,2]输出3说人话就是在每站加一些油、消耗一些油找一个起点使得全程油量不跌到负数。第一反应枚举每个起点classSolutionBrute:defcanCompleteCircuit(self,gas,cost):nlen(gas)forsinrange(n):tank0okTrueforjinrange(n):idx(sj)%n tankgas[idx]-cost[idx]iftank0:okFalsebreakifok:returnsreturn-1维度值说明时间O(n²)每个起点都试一遍空间O(1)n 最大 10^5O(n²) 铁定超时。关键观察亏油点之前的所有起点都不行这是这道题最精妙的推理假设从 start 出发走到 i 时油不够了curr_tank 0。 这意味着 start 到 i 这段路的净收益是负的。 那么从 start1, start2, ..., i 中的任何一站出发 结果只会更差因为少了 start 到那一站的净收益。 所以 start 到 i 之间的所有站都不可能是正确答案 直接把 start 跳到 i1 即可。这个推理让时间从 O(n²) 降到 O(n)——因为每个加油站最多被访问一次。最优解一次遍历维护三个变量变量含义total_tank所有 diff 的总和判断是否有解curr_tank从当前 start 出发累计的油量start当前候选起点classSolution:defcanCompleteCircuit(self,gas:List[int],cost:List[int])-int:total_tank0curr_tank0start0foriinrange(len(gas)):diffgas[i]-cost[i]total_tankdiff curr_tankdiffifcurr_tank0:starti1curr_tank0returnstartiftotal_tank0else-1为什么 total_tank 0 就一定无解total_tank是所有站点的净收益之和。如果总收益是负的说明油不够用不管从哪出发都不可能绕一圈。反之如果总收益 ≥ 0题目保证答案唯一那我们找到的start一定是对的。跑一遍示例 1gas [1, 2, 3, 4, 5] cost [3, 4, 5, 1, 2] diff [-2, -2, -2, 3, 3] i0: diff-2, curr_tank-2 0 → start1, curr_tank0, total-2 i1: diff-2, curr_tank-2 0 → start2, curr_tank0, total-4 i2: diff-2, curr_tank-2 0 → start3, curr_tank0, total-6 i3: diff3, curr_tank3 ≥ 0 → 继续, total-3 i4: diff3, curr_tank6 ≥ 0 → 继续, total0 total0 ≥ 0 → 有解! start3 ✓从站 3 出发加 4 → 跑到 4 剩 3 → 加 5 变 8 → 跑到 0 剩 6 → 加 1 变 7 → 跑到 1 剩 4 → 加 2 变 6 → 跑到 2 剩 2 → 加 3 变 5 → 跑到 3 剩 0 → 正好到达跑一遍示例 2gas [2, 3, 4] cost [3, 4, 3] diff [-1, -1, 1] i0: diff-1, curr_tank-1 0 → start1, curr_tank0, total-1 i1: diff-1, curr_tank-1 0 → start2, curr_tank0, total-2 i2: diff1, curr_tank1 ≥ 0 → 继续, total-1 total-1 0 → 无解! 返回 -1 ✓维度值说明时间O(n)一次遍历空间O(1)三个变量两种解法放在一起看解法时间空间思路暴力枚举O(n²)O(1)每个起点都试一遍一次遍历O(n)O(1)亏油就跳贪心找起点这道题教会我什么失败区间整体跳过是一个通用优化和 LeetCode 55跳跃游戏一样这道题的核心优化是如果某个区间行不通那区间内的所有候选都不行。这种跳过不可能的区间的思路在字符串匹配KMP 的 next 数组和滑动窗口问题里也很常见。先判断有没有解再找解total_tank的作用是快速判断是否有解。如果总油量都不够总消耗那直接返回 -1不用费劲找起点。这种先做可行性检查的思路在很多优化问题里都有——先判断存不存在再去找在哪。答案唯一是一个很强的条件题目说如果存在解则保证唯一。这个条件让我们可以放心地只维护一个start——一旦total_tank ≥ 0我们找到的start一定是唯一正确的那个。如果没有这个保证就需要验证start是否真的可行。完整测试代码fromtypingimportListclassSolution:defcanCompleteCircuit(self,gas:List[int],cost:List[int])-int:total_tank0curr_tank0start0foriinrange(len(gas)):diffgas[i]-cost[i]total_tankdiff curr_tankdiffifcurr_tank0:starti1curr_tank0returnstartiftotal_tank0else-1if__name____main__:sSolution()gas,cost[1,2,3,4,5],[3,4,5,1,2]print(fgas{gas}, cost{cost}→{s.canCompleteCircuit(gas,cost)})gas,cost[2,3,4],[3,4,3]print(fgas{gas}, cost{cost}→{s.canCompleteCircuit(gas,cost)})gas,cost[5,1,2,3,4],[4,4,1,5,1]print(fgas{gas}, cost{cost}→{s.canCompleteCircuit(gas,cost)})gas,cost[3,1,1],[1,2,2]print(fgas{gas}, cost{cost}→{s.canCompleteCircuit(gas,cost)})gas,cost[2],[2]print(fgas{gas}, cost{cost}→{s.canCompleteCircuit(gas,cost)})相关题目推荐LeetCode 55 · 跳跃游戏同样的失败区间跳过思路LeetCode 135 · 分发糖果同样是两遍扫描 贪心LeetCode 918 · 环形子数组的最大和同样是环形数组问题