Cinte's Leetcode Record
0%

134. 加油站

Posted on Edited on In Disqus:
Symbols count in article: 900 Reading time ≈ 1 mins.

134. 加油站

根据答案意思，对于[x, y]，区间，如果从x起步无法到达y之后的一个，则所有x和y区间内部的点起步都无法到达y的后一个点。但内部任意起点可以到达y和y之前加油站由此可以避开许多的起始点判定。

证明:

符合上述条件的区间中存在这样的关系 \[ \sum_{i=x}^{y}gas[i] < \sum_{i=x}^{y}cost[i]\newline \sum_{i=x}^{j}gas[i] >= \sum_{i=x}^{j}cost[i]\ j \in [x, j) \newline \] 第一个式子表明无法到达加油站y的下一个加油站，第二个式子表明从x出发可以到达 y以及y之前的所有加油站。

则对于区间中任意节点z \[ \sum_{i=z}^{y}gas[i]\newline = \sum_{i=x}^{y}gas[i] - \sum_{i=x}^{z - 1}gas[i]\newline < \sum_{i=x}^{y}cost[i] - \sum_{i=x}^{z - 1}gas[i]\newline < \sum_{i=x}^{y}cost[i] - \sum_{i=x}^{z - 1}cost[i]\newline = \sum_{i=z}^{y}cost[i] \]

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
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        int i = 0;
        while(i < n)
        {
            int gasLeft = 0;
            int cnt = 0;
            while(cnt < n)
            {
                int j = (i + cnt) % n;
                gasLeft += gas[j];
                gasLeft -= cost[j];
                if(gasLeft < 0)
                    break;
                ++cnt;
            }
            if(cnt == n)
                return i;
            else
                i += cnt + 1;
        }
        return -1;
    }
};