LeetCode 134 Gas Station加油站环形数组贪心题解——从 O(n²) 暴力到 O(n) 单次遍历【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读本文基于开源仓库 leetcode 的每日一题系列文档 daily/2019-06-04.md系统讲解 LeetCode 134「加油站」Gas Station的两种解法O(n²) 暴力枚举与 O(n) 单次遍历贪心。读者读完后将掌握环形数组遍历的下标处理技巧、某一段不可达则其中任意起点皆不可达的贪心剪枝思想以及用单一变量remain维护剩余油量、以total判定全局可行性的完整推导与可运行代码。一、题目信息与背景时间2019-06-04本项目每日一题第 2 期紧承 2019-06-03 的 14.Longest-Common-PrefixtagArray难度中等所属活动每日一题Daily Challenge由仓库维护者在微信 / QQ 交流群发起每日集中讨论一道题讨论沉淀后收录进 daily/README.md 历史汇总并同步到 daily/answers 目录下的独立解题文件。题目描述原文There are N gas stations along a circular route, where the amount of gas at station i isgas[i].You have a car with an unlimited gas tank and it costscost[i]of gas to travel from station i to its next station (i1). You begin the journey with an empty tank at one of the gas stations.Return the starting gas stations index if you can travel around the circuit once in the clockwise direction, otherwise return -1.翻译成工程语言环形路线上一共有 N 个加油站第 i 个加油站储油量为gas[i]汽车油箱无限大但从第 i 站开到第 i1 站需要消耗cost[i]升油出发时油箱为空必须从某一个加油站出发沿顺时针方向绕行一圈回到起点若存在这样的起点返回其下标否则返回-1。这是一个典型的环形数组 可行性判定问题给定两个等长数组gas与cost求一个起点下标start使得从它出发按(start k) % n的顺序累计净收益gas - cost全程非负。二、思路一暴力求解O(n²)2.1 算法流程最直觉的做法是枚举每一个加油站作为起点模拟完整绕圈过程维护一个remain剩余油量变量每到达一个站点先加油再扣油remain gas[i]; remain - cost[i]若remain一旦小于 0说明当前起点无法走通立即放弃该起点尝试下一个若连续走满 n 站且remain始终非负则当前起点就是答案所有起点都试完后仍未成功返回-1。由于环形数组下标越过n-1后需要回到 0因此需要一个取模/回绕辅助函数。仓库源码 daily/answers/134.gas-station.js 中给出了这一实现function getIndex(index, n) { if (index n - 1) { return index - n; } return index; }2.2 完整代码O(n²)文档原版// bad 时间复杂度 O(n^2) let remain 0; const n gas.length; for (let i 0; i gas.length; i) { remain gas[i]; remain - cost[i]; let count 0; while (remain 0) { count; if (count n) return i; remain gas[getIndex(i count, n)]; remain - cost[getIndex(i count, n)]; } remain 0; } return -1;注getIndex也可用更通用的(i count) % n写法替代两者等价。2.3 复杂度与缺陷外层循环最多执行 n 次内层 while 在极端情况下如全部站点净收益非负也会走到 n因此最坏时间复杂度为 O(n²)空间复杂度 O(1)。当 n 达到 10⁵ 量级LeetCode 数据规模时O(n²) 会超时。更关键的是这种解法浪费了大量重复计算当某个起点在第 j 站失败时中间经过的每一站其实都已经白走了一遍这些中间状态没有被复用。三、思路二贪心单次遍历O(n)3.1 两条核心引理仓库文档 daily/2019-06-04.md 给出了 O(n) 解法的两条基石引理 1区间不可达剪枝如果从站点 i 出发开到站点 j 时走不通remain 0那么从 i 到 j 之间的任意站点 k 出发也一定走不通。前提是 i以及 i 到 k 之间不会拖累总体即走到 k 时remain 0。为什么成立因为从 i 开到 k 的过程remain非负说明 i→k 这段不欠油若 i 带着这个不欠油的状态都到不了 j那么从 k 出发少了一截 i→k 的油量积累油箱从 0 起步必然更加到不了 j。因此一旦在某点失败整个区间 [start, i] 内的站点都可以被排除无需逐一尝试。引理 2全局可行性判据如果cost总和大于gas总和总消耗 总补给那么无论如何都无法走完一圈反之若总补给 ≥ 总消耗则一定存在至少一个可行的起点。这等价于全路程总净收益total Σ(gas[i]) - Σ(cost[i])。total 0时无解total 0时必有解且解恰为贪心过程中最后一次把remain清零后重置的那个start。3.2 算法流程维护三个变量做一次遍历total累计全局净收益gas[i] - cost[i]用于最终判定是否存在可行起点remain以当前候选start为起点的局部累计净收益一旦 0说明该起点不可行start当前候选起点下标remain 0时重置为i 1。3.3 完整代码O(n)文档原版const n gas.length; let total 0; let remain 0; let start 0; for (let i 0; i n; i) { total gas[i]; total - cost[i]; remain gas[i]; remain - cost[i]; // 如果 remain 0说明从 start 到 i 走不通 // 并且从 start 到 i 走不通那么所有 solution 中包含 start 到 i 的肯定都走不通 // 因此我们重新从 i 1 开始作为 start if (remain 0) { remain 0; start i 1; } } // 事实上我们遍历一遍也就确定了每一个元素作为 start 是否可以走完一圈 // 如果 cost 总和大于 gas 总和无论如何也无法走到终点 return total 0 ? start : -1;3.4 源码佐证该解法与仓库中的正式提交完全一致见 daily/answers/134.gas-station.js文件以var canCompleteCircuit function(gas, cost)封装暴力解法被完整注释保留用于对照L19-L34O(n) 解法为最终提交L37-L60。从源码结构看getIndex辅助函数仅被暴力版本使用O(n) 版本通过失败即重置起点天然回避了环形下标的显式取模。3.5 复杂度时间O(n)单次线性遍历无嵌套循环空间O(1)仅三个常数变量。四、正确性推导与手算验证4.1 为什么遍历一遍就能确定答案遍历过程中start的更新遵循以下不变量[0, i]范围内所有下标中只有start可能是可行起点[start, i]之间的任意下标都已被证明不可行。每次remain 0时根据引理 1[start, i]整段作废新的候选只能从i 1开始。最终若total 0根据引理 2 必存在解而这个解恰恰就是最后一次重置后的start——因为[0, start - 1]的每一段前缀都已被引理 1 剪枝只有start幸存。4.2 手工示例示例 A有解gas [1, 2, 3, 4, 5] cost [3, 4, 5, 1, 2]igas[i]-cost[i]remaintotalstart0-2-2 → 清零-211-2-2 → 清零-422-2-2 → 清零-63333-3343603total 0 0返回start 3。验证从 3 出发油量变化 0→3→6→4→2→0全程非负绕圈成功。✔示例 B无解gas [1, 2, 3] cost [2, 2, 4]total (1-2)(2-2)(3-4) -2 0直接返回-1。即使中间某个remain曾非负全局总净收益为负也注定无法闭环。✔五、边界情况与常见坑点单站场景n 1gas[0] cost[0]时返回 0否则返回 -1上述代码天然覆盖恰好等于total 0是允许的油箱到达终点时恰为 0 也视为成功因此判据是total 0而非total 0环形下标暴力解法必须处理i count越过数组末尾的回绕getIndex或取模O(n) 解法无需显式处理因为候选起点只会单向前进remain清零时机必须在remain 0时先清零再更新start i 1顺序颠倒会引入上一段失败区间的负油量污染重复起点start重置为i 1后可能等于 n当最后一段也失败此时total 0必然成立返回 -1不会出现越界访问。六、总结一道题两种思想方案核心思想时间复杂度空间复杂度适用场景暴力枚举枚举起点 模拟绕圈O(n²)O(1)小数据量、理解题意贪心单次遍历区间不可达剪枝 全局可行性判据O(n)O(1)任意规模面试与竞赛首选134. Gas Station的价值不在于题本身而在于它同时承载了环形数组处理与贪心剪枝两大高频考点环形数组问题环形子数组最大和、循环链表等都依赖% n或回绕下标处理一旦某段失败区间内所有起点全部作废的剪枝思想与最大子段和、买卖股票等问题中的贪心套路一脉相承全局变量total与局部变量remain的分工是可行性与最优性分开判定这一通用建模手法的典型示范。读者可结合 daily/answers/134.gas-station.js 对照源码进行单步调试并将本文推导过程补充为笔记沉淀这正是本项目每日一题活动的初衷题目经 daily/README.md 收录后最终会筛选进入 problems 题库模块形成从讨论到沉淀的完整闭环。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考