AlgoViz Lab交互式算法学习Algorithms first
加油站 · 交互式算法学习
找到能绕环路一周的唯一出发加油站。
#134 · 数组 / 字符串
加油站
Gas Station
gas = [1,2,3,4,5], cost = [3,4,5,1,2]线性序列4 个关键状态
步骤 1从 0 出发后油量为负，起点移到 1。
start=1, tank=0-2
0-2
1-2
23
33
4推荐
总量判断 + 贪心起点
时间
O(n)空间 O(1)总油量足够时一定有解；当前累计油量为负，起点只能移到下一站。
1function canCompleteCircuit(gas, cost) {2 let total = 0,3 tank = 0,4 start = 0;5 for (let i = 0; i < gas.length; i++) {6 const gain = gas[i] - cost[i];7 total += gain;8 tank += gain;9 if (tank < 0) {10 start = i + 1;11 tank = 0;12 }13 }14 return total >= 0 ? start : -1;15}多语言参考
来源 · CC BY-SA 4.0 ↗Java · C++ · Go
这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。
1class Solution {2 public int canCompleteCircuit(int[] gas, int[] cost) {3 int n = gas.length;4 int i = n - 1, j = n - 1;5 int cnt = 0, s = 0;6 while (cnt < n) {7 s += gas[j] - cost[j];8 ++cnt;9 j = (j + 1) % n;10 while (s < 0 && cnt < n) {11 --i;12 s += gas[i] - cost[i];13 ++cnt;14 }15 }16 return s < 0 ? -1 : i;17 }18}交互式算法学习
从执行步骤真正理解 LeetCode 经典 150
本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。
AlgoViz Lab
加油站 · 解法对比
找到能绕环路一周的唯一出发加油站。
- 测试用例
gas = [1,2,3,4,5], cost = [3,4,5,1,2]- 题目分类
- 数组 / 字符串
- 解法对比
- 2
逐站模拟
把每个站都当作起点，模拟油量直到失败或绕回。
- 时间
O(n²)- 空间
O(1)
总量判断 + 贪心起点
总油量足够时一定有解；当前累计油量为负，起点只能移到下一站。
- 时间
O(n)- 空间
O(1)
为什么有效
把每个站都当作起点，模拟油量直到失败或绕回。
关键不变量
每一步都保持当前方法的已处理部分正确，并朝“找到能绕环路一周的唯一出发加油站。”推进。
易错点
- 先确认输入边界与下标范围。
- 代码、变量状态与动画步骤应保持一致。
边界情况
- 空输入或最小规模输入。
- 重复值、极端顺序或退化结构。
更多案例
gas = [1,2,3,4,5], cost = [3,4,5,1,2]找到能绕环路一周的唯一出发加油站。把每个站都当作起点，模拟油量直到失败或绕回。