FlareBall's Blog
0%

134.加油站

Posted on In ,

贪心

首先，总油量 ≥ 总消耗量是存在解得充分必要条件。

证明：

设 net[i] = gas[i] - cost[i]（每个加油站的净收益）

条件1：必要性

如果总油量 < 总消耗量，即 Σnet[i] < 0

那么无论如何选择起点，总油量都不够绕一圈

必要条件成立

**条件2：充分性

假设 Σnet[i] ≥ 0，但不存在任何起点可以完成环路。

这意味着：对于每一个可能的起点 k，在绕行过程中都会在某个点出现油量不足。

假设从起点 k出发，在到达点 m时第一次出现油量不足，那么：

  • 从 k到 m的净收益总和 < 0
  • 由于总净收益 ≥ 0，那么从 m回到 k的净收益总和必须 > 0
  • 矛盾！因为如果从 m回到 k的净收益 > 0，那么从 m出发应该能够完成环路

充分条件成立

因此，只需要

  • 1 统计总油量 ≥ 总消耗量

  • 2 满足 1 的时候找到起点，实现方式为当我们发现某段路程总消耗量 ≥总油量为负时候把下一个当作起点即可

时间复杂度：$O(n)$

空间复杂度：$O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length, sumGas = 0, curGas = 0, start = 0;
        for (int i = 0; i < n; ++i) {
            sumGas += gas[i] - cost[i];
            curGas += gas[i] - cost[i];
            if (curGas < 0) {
                curGas = 0;
                start = i + 1;
            }
        }
        return sumGas >= 0 ? start : -1;
    }
}