LeetCode 134.加油站：贪心策略下的环形路线可行性判断

一、问题定义与核心挑战

1.1 问题描述

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中一个加油站出发，开始时油箱为空。如果可以绕环路行驶一周，则返回出发时的加油站编号；否则，返回 -1。

1.2 核心特征

• 环形结构：最后一个加油站的下一站是第一个加油站
• 油量约束：行驶过程中油箱不能为负
• 唯一性：如果存在解，则保证唯一

示例：

• 输入：gas = [1,2,3,4,5], cost = [3,4,5,1,2]
• 输出：3（从索引3出发，可绕环一周）

二、解题思路：贪心算法的局部与全局判断

2.1 核心思想

通过两个关键指标判断可行的起点：

1. 全局可行性：总加油量 totalSum 必须大于等于总消耗量，否则无法绕环
2. 局部可行性：从候选起点开始累积的油量 curSum 不能为负，若为负则该起点不可行，需重新选择下一个起点

2.2 直观理解

把环形路线想象成一段连续的路程，每个加油站的 gas[i]-cost[i] 表示该站点的"净收益"：

• 若总净收益为负，必然无法绕环
• 若局部净收益累积为负，说明从当前起点到该点的路段无法通过，需尝试新起点

三、代码逐行解析

3.1 变量初始化

int curSum = 0;    // 当前累积净收益
int totalSum = 0;  // 总净收益
int index = 0;     // 候选起点索引

3.2 遍历计算与判断

for (int i = 0; i < cost.length; i++) {
    curSum += gas[i] - cost[i];  // 累积当前净收益
    totalSum += gas[i] - cost[i];  // 累积总净收益
    
    // 若当前累积净收益为负，说明从当前起点到i不可行
    if (curSum < 0) {
        index = (i + 1) % cost.length;  // 重置起点为i+1
        curSum = 0;  // 重置当前累积
    }
}

3.3 全局判断与结果返回

if (totalSum < 0) return -1;  // 总净收益为负，无法绕环
return index;  // 返回可行起点

四、算法执行过程演示

以 gas = [1,2,3,4,5], cost = [3,4,5,1,2] 为例：

总净收益 totalSum=0 ≥ 0，返回 index=3，符合预期。

五、核心逻辑深度解析

5.1 为什么重置起点为 i+1？

若从起点 start 到 i 的累积净收益为负，说明：

• 从 start 到 i 之间的任何站点都不能作为新起点（因为中间任何点的累积收益只会更小）
• 必须从 i+1 开始重新尝试，这是贪心策略的关键优化

5.2 为什么总净收益非负就一定有解？

• 总净收益 totalSum ≥ 0 是存在解的必要条件（全局可行）
• 算法通过局部累积判断已排除了所有不可行起点，剩余的 index 必然是可行起点（题目保证解的唯一性）

5.3 环形结构的处理

通过 (i + 1) % cost.length 处理环形边界，当 i 是最后一个元素时，i+1 会正确指向第一个元素。

六、算法复杂度分析

• 时间复杂度：O(n)，仅需遍历数组一次（n 为加油站数量）
• 空间复杂度：O(1)，仅使用常数个变量

七、常见误区与优化说明

7.1 误区1：尝试所有可能的起点

暴力解法会对每个起点进行模拟行驶，时间复杂度为 O(n²)，而贪心算法通过一次遍历即可找到解，效率更高。

7.2 误区2：忽略环形结构的处理

实际代码中无需特殊处理环形，因为遍历到最后一个元素后，index 会自然指向正确的起点，且总净收益判断已保证全局可行性。

7.3 优化点：提前终止判断

当 totalSum 已确定为负时，可提前终止循环，但实际优化效果有限，因为仍需遍历完数组才能计算 totalSum。

八、总结：贪心算法的分段优化

本题的贪心策略通过"分段排除"不可行起点，实现了高效求解：

1. 用 curSum 跟踪当前路段的可行性，及时重置起点
2. 用 totalSum 保证全局可行性
3. 利用问题的唯一性，无需验证最后找到的起点

这种"局部排除+全局验证"的思路，可应用于其他环形路线或分段优化问题。
代码的核心在于通过两个累加器分别跟踪局部和全局的净收益，通过及时重置起点排除不可行路线，最终在一次遍历中找到可行起点或确定无解，体现了贪心算法的高效性。