LeetCode 134. 加油站（O(n)时间+O(1)空间最优解）
✨ 本文针对 LeetCode 中等难度题目 134. 加油站，提供一种时间复杂度 O(n)、空间复杂度 O(1) 的最优解法，结合具体思路推导和代码实现，帮你快速吃透这道题。
一、题目描述
在一条环路上有n个加油站，其中第i个加油站有汽油gas[i]升。
你有一辆油箱容量无限的的汽车，从第i个加油站开往第i+1个加油站需要消耗汽油cost[i]升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组gas和cost，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回-1。如果存在解，则保证它是唯一的。
二、解题思路推导
核心思想
利用「贪心策略」，通过一次遍历找到合法起点，无需重复模拟。核心逻辑是：如果从起点 i 到 j 时汽油耗尽，那么 i 到 j 之间的所有站点都不能作为起点，直接将起点更新为 j+1。
变量定义
i：标记当前候选起点，初始设为最后一个站点（n-1），反向推导更高效。j：标记当前行驶到的站点，从起点 i 开始向前移动（循环遍历）。s：当前油箱剩余汽油量，初始为 0。cnt：当前已行驶过的加油站数量，用于判断是否完成一周循环。
执行步骤
初始化：
i = n-1，j = n-1，s = 0，cnt = 0。开始行驶：移动
j（循环左移，即 j = (j-1) % n，也可正向遍历，此处反向更贴合初始起点设置），并更新剩余汽油s += gas[j] - cost[j]（表示从 j 站开到 j+1 站的汽油变化）。判断剩余汽油：若
s < 0，说明当前起点i无法支撑到j站，需将起点i循环左移（i = (i-1) % n），同时将s加上gas[i] - cost[i]（补充从新起点 i 到原起点 i+1 的汽油量），直至s >= 0。计数判断：每行驶一个站点，
cnt += 1。当cnt == n时，说明已完成一周循环，停止遍历。结果判断：若此时
s >= 0，则i是合法起点，返回i；否则返回 -1（无合法起点）。
逻辑验证
为什么这样能找到合法起点？假设从 i 到 j 时 s 为负，说明 i 到 j 之间的任何站点 k 都无法作为起点——因为从 k 出发到 j 时，汽油量只会比从 i 出发到 j 时更少（i 到 k 之间的汽油消耗已导致亏损）。因此直接跳过中间站点，将起点更新为 j+1，减少无效遍历。
三、代码实现（Java）
Java 实现
class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { int n = gas.length; int i = n - 1, j = n - 1; int cnt = 0, s = 0; while (cnt < n) { s += gas[j] - cost[j]; ++cnt; j = (j + 1) % n; while (s < 0 && cnt < n) { --i; s += gas[i] - cost[i]; ++cnt; } } return s < 0 ? -1 : i; } }四、复杂度分析
时间复杂度 O(n)：每个站点最多被访问两次（一次被 j 遍历，一次被 i 遍历），整体遍历次数为 O(n)，无嵌套重复遍历。
空间复杂度 O(1)：仅使用 4 个额外变量（i、j、s、cnt），不依赖额外数组或数据结构，空间开销恒定。
五、测试用例验证
示例 1 验证
输入：gas = [1,2,3,4,5], cost = [3,4,5,1,2]
执行过程：
初始 i=4, j=4, s=0, cnt=0。
j=4：s += 5-2=3 → s=3，cnt=1，j=3。s≥0，无需移动i。
j=3：s +=4-1=3 → s=6，cnt=2，j=2。
j=2：s +=3-5=-2 → s=4，cnt=3，j=1。
j=1：s +=2-4=-2 → s=2，cnt=4，j=0。
j=0：s +=1-3=-2 → s=0，cnt=5（等于n=5）。循环结束，s≥0，返回i=3（过程中i未移动，最终i=3）。
示例 2 验证
输入：gas = [2,3,4], cost = [3,4,3]
执行结束后 cnt=3，但 s= (4-3)+(3-4)+(2-3) = 1-1-1 = -1 <0，返回-1。
六、总结
本题的关键是利用贪心策略跳过无效起点，将时间复杂度从 O(n²) 优化到 O(n)。核心逻辑是「无效起点区间内的所有站点均无效」，通过反向推导（初始起点设为 n-1）简化遍历过程，同时保证空间复杂度最优。
这种思路不仅适用于本题，还可迁移到类似「寻找循环有效起点」的贪心问题中，建议结合代码多模拟几遍执行过程，加深对贪心逻辑的理解。
💡 如果你有其他解法或疑问，欢迎在评论区留言交流！