求解思路
这道题我们把环形数组想象成展开的线性数组（通过取模实现），然后用一个窗口[l, r)来表示从l站出发能走到的范围，窗口内维护一个油量累加和sum。
每次尝试让窗口右边界r向右扩展，如果加上r站的净油量（gas[r] - cost[r]）后sum还是非负的，说明能走到r站，就继续扩展；
一旦发现扩展到某站会让sum变负，说明从l出发走不通，此时直接跳过整个窗口，让新起点从r+1开始尝试。
这样做的合理性在于，如果从l出发走不到r，那么从l到r之间的任何一站出发也走不到r（因为中间任何一站的初始油量都不如从l站累积过来的多），所以可以直接跳过这些站点，大大减少了尝试次数。当某个起点l的窗口成功扩展到覆盖n个站点时，就找到了答案。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public static int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
// 窗口范围[l, r)，左闭右开
for (int l = 0, r = 0, sum; l < n; l = r + 1, r = l) {
sum = 0;
// 尝试扩展窗口右边界
while (sum + gas[r % n] - cost[r % n] >= 0) {
// 检查是否已经转了一圈
if (r - l + 1 == n) {
return l;
}
// r位置进入窗口，累加净油量
sum += gas[r % n] - cost[r % n];
r++;
}
}
return -1;
}
|
如果觉得有帮助，欢迎点赞、关注、转发~