Gas Station Problem

Posted on Edited on In Views: 55

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique

134. Gas Station

Solution

枚举所有可能, 并通过寻找规律来去除冗余计算.

我们发现:

如果选择站点i作为起点「恰好」无法走到站点j，那么i和j中间的任意站点k都不可能作为起点.

证明:

假设tank记录当前油箱中的油量，如果从站点i出发（tank = 0），走到j时恰好出现tank < 0的情况，那说明走到i, j之间的任意站点k时都满足tank >= 0.

Given sequence: Tank(i),⋯,Tank(k),⋯,Tank(j) ∀k∈{i+1,...,j−1}, Tank(k)≥0 序列从k开始为: Tank(k)≥0,Tank(k+1)≥0,⋯,Tank(j)<0 而如果以k作为起点, 相当于在站点k时tank=0, 则序列从k开始变成: 0,Tank(k+1)−Tank(k),⋯,⋯,Tank(j)−Tank(k) 在新序列的每一个站点的油箱容量都比之前少. 已知Tank(j)<0, 则必定有Tank(j)−Tank(k)<0. 因此∀k∈{i+1,...,j−1}, k不可能作为起点.

此外, j也不能作为起点. 因为既然j是第一个恰好出现tank < 0的点, 必定有gas[j-1] - cost[j-1] < 0. 否则有gas[j] - cost[j] >= 0且tank[j]<0, 此时点j-1满足:

1
tank[j-1] = tank[i] - (gas[j-1] - cost[j-1] ) <= tank[j] < 0

与前提矛盾.

因此, 下一个可能的起始站点是j+1.

Code

如果总油量小于总的消耗, 那么起点从0一直遍历到N-1都不符合条件. 因此预先排除掉这个无解的情况.

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
public int canCompleteCircuit(int[] gas, int[] cost) {
        int N = gas.length;

        int sum = 0;
        for( int i = 0; i < N; i++ )
            sum += gas[i] - cost[i];
        if(sum < 0) // 总油量小于总的消耗，无解
            return -1;

        int start = 0;
        int tank = 0;
        for( int i = 0; i < N; i++ )
        {
            tank += gas[i] - cost[i];
            if(tank < 0)
            {
                // 
                // 所以可能的起点应该是 i + 1 
                start = i+1;
                tank=0;
                
                if( start == N-1 )
                    start = 0; //无法从 start 走到 N-1, 下一个可能的起点是N. 由于路线是循环的, 站点N也就是站点0.
            }
        }
        return start;
    }
  • Complexity: O(N). N = number of gas stations.