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 核心思想
通过两个关键指标判断可行的起点：
- 全局可行性：总加油量
totalSum必须大于等于总消耗量，否则无法绕环 - 局部可行性：从候选起点开始累积的油量
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+1curSum = 0; // 重置当前累积}
}
3.3 全局判断与结果返回
if (totalSum < 0) return -1; // 总净收益为负，无法绕环
return index; // 返回可行起点
四、算法执行过程演示
以 gas = [1,2,3,4,5], cost = [3,4,5,1,2] 为例：
索引 i | gas[i]-cost[i] | curSum | totalSum | 操作 | index |
|---|---|---|---|---|---|
| 0 | 1-3 = -2 | -2 | -2 | curSum<0 → 重置index=1，curSum=0 | 1 |
| 1 | 2-4 = -2 | -2 | -4 | curSum<0 → 重置index=2，curSum=0 | 2 |
| 2 | 3-5 = -2 | -2 | -6 | curSum<0 → 重置index=3，curSum=0 | 3 |
| 3 | 4-1 = 3 | 3 | -3 | 正常累积 | 3 |
| 4 | 5-2 = 3 | 6 | 0 | 正常累积 | 3 |
总净收益 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。
八、总结：贪心算法的分段优化
本题的贪心策略通过"分段排除"不可行起点，实现了高效求解：
- 用
curSum跟踪当前路段的可行性，及时重置起点 - 用
totalSum保证全局可行性 - 利用问题的唯一性，无需验证最后找到的起点
这种"局部排除+全局验证"的思路，可应用于其他环形路线或分段优化问题。
代码的核心在于通过两个累加器分别跟踪局部和全局的净收益，通过及时重置起点排除不可行路线，最终在一次遍历中找到可行起点或确定无解，体现了贪心算法的高效性。