Gas Station

134. 加油站

分析

模拟遍历：
- 从每个加油站 i 出发，模拟一圈是否能顺利到达终点
剩余油量判断：
- 每经过一个加油站，更新剩余油量 oil = oil + gas[k] - cost[k]
- 如果油量不足 oil < 0，说明从当前起点 i 无法完成一圈
跳过不可行区间：
- 如果从 i 出发失败，则从 i + step + 1 开始继续尝试，因为 i 到 i + step 之间的起点也无法成功
终止条件：
- 如果某次尝试走满了 n 步（即 step == n），说明该起点 i 能绕一圈，返回 i
- 如果所有加油站都尝试失败，则返回 -1

时间复杂度

时间复杂度 O(n)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


class Solution
{
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost)
    {
        int n = gas.size(), step = 0;  // n 为加油站数量

        for (int i = 0; i < n;)  // 遍历每个加油站作为起点
        {
            int oil = 0;  // 当前剩余油量
            for (step = 0; step < n; ++step)
            {
                int k = (i + step) % n;  // 环形遍历加油站
                oil += gas[k] - cost[k];  // 更新剩余油量

                if (oil < 0)  // 如果油量不足，停止尝试
                    break;
            }

            if (step == n)  // 成功绕一圈
                return i;

            i = i + step + 1;  // 跳过失败区间，尝试下一个起点
        }

        return -1;  // 没有找到可行解
    }
};