力扣(LeetCode)134. 加油站(C++)

贪心

考虑暴力，枚举所有点作为起点，每个点先加油，再尝试前往下一个点，剩余油量大于等于 $0$ ，就可以走下去。枚举所有点的所有路径，时间复杂度 $O(n^2)$ ，对于本题规模 $TLE$ 。

优化枚举，考虑一个性质 : 对于起点 $start$ ，它能到达的最远点 $end$ 。 闭区间 $start$ 到 $end-1$ 的所有点，最远达到位置不会超过 $end$ 。这是因为，对于从 $start$ 出发的点，如果它最远能到 $end$ ，那么它在路径上都是带油或没油到某一点的 ，在闭区间上找一起点，有油都到不了 $end$ ，没油出发更到不了 $end$ 。

基于上一性质，我们在枚举起点时，找起点能到达的最远距离，仅当最远距离为所有点的长度，有解，否则更新起点为能到达的最远点。

提示 : $i$ 是起点， $j$ 是从 $i$ 出发的最远距离。由于数组是个环，用取模操作得到当前位置。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        int rem = 0;
        for(int i = 0,j;i<n;){
            for(j = 0;j<n;j++){
                int k = (i+j) % n;
                rem = rem + gas[k] -cost[k];
                if(rem<0) break;
            }
            if(n==j) return i;
            i = i + j + 1;
            rem = 0;
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1. 时间复杂度 : $O(n)$ ， $n$ 是加油站的数量，最多遍历每个点两遍，时间复杂度 $O(n)$ 。
2. 空间复杂度 : $O(1)$ ， 只使用常量级空间 。

AC