从更本质的角度去看「加油站」问题
题目描述
这是 LeetCode 上的 「134. 加油站」 ，难度为 「中等」。
在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
说明:
- 如果题目有解，该答案即为唯一答案。
- 输入数组均为非空数组，且长度相同。
- 输入数组中的元素均为非负数。
示例 1:
输入:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。
示例 2:
输入:
gas = [2,3,4]
cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。
基本分析/朴素解法
这是一道比较经典的题目。
估计在 LeetCode 也是有一段时间了，所以连数据范围都没有。
我这里直接规定一下数据范围为
，这意味着我们不能使用
做法了。
但朴素做法往往是优化的出发点，所以我们还是先分析一下，朴素的做法是怎么样的：
- 题目要求「合法起点」的下标，因此我们可以枚举所有的「起点」
- 然后按照「油量 & 成本」模拟一遍，看是否能走完一圈
共有
个「起点」，检查某个「起点」合法性的复杂度是
的。因此整体复杂度为
的。
代码：
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
for (int start = 0; start < n; start++) {
// 直接跳过第一步都不满足的起点
if (gas[start] < cost[start]) continue;
// 剩余油量
int cur = gas[start] - cost[start];
// 所在位置
int idx = (start + 1) % n;
while (idx != start) {
cur += gas[idx] - cost[idx];
// 如果剩余油量为负数，说明无法离开当前位置，走到下一位置
if (cur < 0) break;
idx = (idx + 1) % n;
}
if (idx == start) return start;
}
return -1;
}
}
- 时间复杂度：
- 空间复杂度：
PS. 在 LeetCode 上提交了一下，是可以过的 ?
KMP/DFA
不考虑我们跳过那些第一步就不满足的起点的话，将上述解法中的两个主要逻辑“单独”拎出来看，都是无法优化的：
- 在没做任何操作之前，我们无法知道哪些起点是不合法的
- 没有比
更低的复杂度可以验证一个起点的合法性
因此只能使用
解法？
并不是。单独看无法优化，合在一起则可以：随着某个起点「合法性验证」失败，我们可以否决掉一些「必然不合法」的方案。
什么意思呢？
在朴素解法中，当我们验证了某个起点
失败（无法走完一圈）之后，我们接下来会去尝试验证起点
。
这时候验证
失败过程中产生的“信息”，其实并没有贡献到之后的算法中。
事实上，起点
验证失败，其实是意味存在某个位置
使得「当前油量」为负数。而这个位置
就是验证起点
这过程中产生的“信息”。
它可以产生的价值是：在位置
和位置
之间的所有位置，都不可能是一个合法起点。也就是说，随着起点
验证失败，我们可以否决掉方案不仅仅是位置
，而是
这些位置。
我们可以证明为什么会有这样的性质：
首先，可以明确的是：因为 gas 数组和 cost 数组是给定的，因此每个位置的「净消耗」是固定的，与从哪个「起点」出发无关。
净消耗是指该位置提供的「油量」和「到达下一位置的油耗」，也就是 gas[i] 和 cast[i] 之间的差值。
证明过程如图：
因此，当有了这个优化之后，我们每个位置其实只会被遍历常数次：当位置
作为「起点」验证失败后，验证过程中遍历过的位置就不需要再作为「起点」被验证了。
代码：
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
for (int start = 0; start < n; ) {
if (gas[start] < cost[start]) {
start++;
} else {
int cur = gas[start] - cost[start];
int idx = start + 1;
while (idx % n != start) {
cur += gas[idx % n] - cost[idx % n];
if (cur < 0) break;
idx++;
}
if (idx % n == start) return start;
else start = idx;
}
}
return -1;
}
}
- 时间复杂度：
- 空间复杂度：
总结
看到这里，你可以已经理解了
解法是怎么来的了。
但可能还不清楚这个优化思路的本质是什么，其实这个优化的本质与 KMP 为什么可以做到线性匹配如出一辙。
本质都是利用某次匹配（验证）过程产生的“信息”，来加速之后的匹配（验证）过程（否决掉一些必然合法的方案）。
在我写过的 KMP 题解里，有这么一句原话：
❝当我们的原串指针从
i位置后移到j位置，不仅仅代表着「原串」下标范围为
的字符与「匹配串」匹配或者不匹配，更是在否决那些以「原串」下标范围为
为「匹配发起点」的子集。 ❞
所以，从更本质的角度出发，这道题其实是一道「KMP」思想应用题，或者说广泛性的「DFA」题。
其他
在写「总结」部分的时候，我还特意去看了一下题解区，没有人提到过「KMP」和「DFA」，几乎所有题解都停留在题目标签「贪心算法」的角度去思考。
这是不对的，题目标签的拟定很大程度取决于「写这个标签的人的水平」和「ta 当时看这道题的思考角度」，是一个主观的结果。
学习算法和数据结构，应该是去理解每个算法和数据结构的“某个操作”为什么能够带来优化效果，并将该优化效果的“底层思想”挖掘出来，应用到我们没见过的问题中，这才是真正的“学习”。
最后
这是我们「刷穿 LeetCode」系列文章的第 No.134 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。