LeetCode 134 Gas Station（加油站）环形数组贪心题解——从 O(n²) 暴力到 O(n) 单次遍历

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-Prefix）
• tag：Array
• 难度：中等
• 所属活动：每日一题（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 (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

翻译成工程语言：

1. 环形路线上一共有 N 个加油站，第 i 个加油站储油量为gas[i]；
2. 汽车油箱无限大，但从第 i 站开到第 i+1 站需要消耗cost[i]升油；
3. 出发时油箱为空，必须从某一个加油站出发，沿顺时针方向绕行一圈回到起点；
4. 若存在这样的起点，返回其下标，否则返回-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-L34），O(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]

i	gas[i]-cost[i]	remain	total	start
0	-2	-2 → 清零	-2	1
1	-2	-2 → 清零	-4	2
2	-2	-2 → 清零	-6	3
3	+3	3	-3	3
4	+3	6	0	3

total = 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曾非负，全局总净收益为负也注定无法闭环。✔

---

五、边界情况与常见坑点

1. 单站场景（n = 1）：gas[0] >= cost[0]时返回 0，否则返回 -1；上述代码天然覆盖；
2. 恰好等于：total == 0是允许的（油箱到达终点时恰为 0 也视为成功），因此判据是total >= 0而非total > 0；
3. 环形下标：暴力解法必须处理i + count越过数组末尾的回绕（getIndex或取模）；O(n) 解法无需显式处理，因为候选起点只会单向前进；
4. remain清零时机：必须在remain < 0时先清零再更新start = i + 1，顺序颠倒会引入上一段失败区间的"负油量"污染；
5. 重复起点：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