加油站问题如何用贪心找到出发点？（LeetCode 134）

简化版

环形路上有 n 个加油站，第 i 站有油 gas[i]，从 i 开到 i+1 站要耗油 cost[i]。油箱无限、初始为空，问能否从某个站出发绕一圈回到起点，能则返回出发站下标（保证唯一），否则返回 -1。贪心策略：若总油量 ≥ 总消耗，一定有解；找起点时，从 0 开始累加 gas[i]-cost[i]，一旦累计油量变负，说明当前起点到 i 之间任何站都当不了起点，把起点跳到 i+1 并重置累计。

详细版

int canCompleteCircuit(int[] gas, int[] cost) {
    int total = 0;      // 全程总净油量，判断是否有解
    int tank = 0;       // 从当前候选起点出发的累计净油量
    int start = 0;      // 候选起点
    for (int i = 0; i < gas.length; i++) {
        int diff = gas[i] - cost[i];
        total += diff;
        tank += diff;
        if (tank < 0) {         // 从 start 到 i 走不通
            start = i + 1;      // 起点只能在 i 之后
            tank = 0;           // 重新从 i+1 累计
        }
    }
    return total >= 0 ? start : -1;
}

total：所有 gas[i]-cost[i] 之和。total < 0 直接无解（总油不够，谁当起点都绕不完）。
tank：从当前候选 start 出发，开到 i 时油箱剩余净油。tank < 0 说明这段撑不住。
起点跳跃：一旦 tank<0，start 直接跳到 i+1，不用逐个回退。
复杂度：O(n) 时间、O(1) 空间，一趟遍历。

完整版教学

一、两个核心结论先记住

这题的贪心建立在两个可证明的结论上：

若 sum(gas) >= sum(cost)（总油 ≥ 总耗），则一定有唯一解；反之无解。
若从站 A 出发，走到站 B 时油箱首次变负，那么 A、A+1、…、B 之间的任何一站都不能作为起点，起点必然在 B+1 或更后。

把这两点想通，代码就是自然的一趟扫描。

二、结论 1：总油够就必有解

把每站的净油量定义为 diff[i] = gas[i] - cost[i]。绕一圈的总净油是 total = sum(diff)。

如果 total < 0：无论从哪出发，走完一圈的净油都是负的，油箱必然在某处见底 → 无解。
如果 total >= 0：一定存在一个起点能走完（下面结论 2 会给出构造）。

这是个漂亮的整体性结论：是否有解只看总量，与起点无关；起点在哪是另一个问题。

三、结论 2：起点为什么能「跳跃」而不用回退

假设从 start 出发，一路累加 tank，在下标 i 处第一次 tank < 0。这说明区间 [start, i] 的净油和为负。现在问：[start, i] 里的某个中间站 j 能当起点吗？

不能。 因为从 start 到 j 这段的累计油量一直是 ≥ 0 的（i 是第一次变负的点，j 在 i 之前，所以走到 j 时 tank ≥ 0）。也就是说，「从 start 出发到 j」时油箱还有富余油。如果改成「从 j 出发」，就少了这段富余的垫底油，情况只会更糟——start 都到不了终点，起点更靠后的 j 更到不了。

所以 [start, i] 内所有站都被排除，起点直接跳到 i+1，tank 清零重新计。这就是 O(n) 一趟扫描的关键：不回退、不重试。

四、为什么最后 start 就是答案

如果 total >= 0，设最终 start 停在某个下标。从这个 start 到数组末尾，累计 tank 始终没变负（否则 start 还会往后跳）。而 start 之前的那部分（下标 0 到 start-1），它们的净油和是负的（正是这些负段把 start 逼到现在的位置）。既然总和 total >= 0，那么 [start, n-1] 这段的净油和 = total - (前面负的部分) >= 0，足够覆盖前面欠的油。于是从 start 绕一圈：先攒够 [start, n-1] 的正油量，再回来填补 [0, start-1] 的亏空，恰好能走完。所以 start 就是答案。

五、常见误区

误区 1：用双重循环暴力枚举每个起点。O(n²) 能过小数据，但贪心一趟 O(n) 才是考点。
误区 2：把 total 和 tank 混用。total 是全局判有无解，tank 是局部判当前起点是否撑得住，两者职责不同、缺一不可。
误区 3：忘了环形。看似要处理绕回开头，但因为「总量够就有解」，实际上一趟线性扫描 + 起点跳跃已隐含处理了环形，不用真的取模跑两圈。

还要区分 tank 与 total：前者只判断当前候选起点是否失败，失败后清零；后者累计整圈净油量，决定是否存在任何解。把二者合并成一个变量会在重置时丢失全局可行性信息。

六、贪心选择为什么不会堵死未来

本题每一步选择是：总油量足够时，扫描累计油量一旦为负，就把下一站设为新起点并清空局部累计。

正确性不能只靠直觉，核心证明是：从旧起点到失败点的任何中间站拥有更少的前缀余量，也无法越过失败点，因此整段起点可一起排除。这说明任意最优方案都能调整为包含当前贪心选择的方案，且目标值不会变差。

排序或预处理，建立可比较的选择顺序
维护“当前选择给未来留下的有效边界”
若候选不劣于现有边界，则提交选择并更新状态

数字推演：gas=[1,2,3,4,5], cost=[3,4,5,1,2] 总差为0，扫描在下标2前失败，最终起点3可绕一圈。

记忆钩子：贪心不是“选眼前最大”，而是选一个能被交换论证证明、对未来最宽松的代表。

七、退化边界、复杂度与反例检查

实现边界是：先用 total<0 判无解；局部 tank 清零不影响 total；题目若保证唯一解才可忽略多解讨论。

检查项	必须回答
排序键	为什么按这个维度和方向排序
局部选择	它保留了什么未来可能性
正确性	交换、领先或反证中的哪一种
失败边界	哪个题目条件一改就不能贪心
复杂度	排序成本与扫描成本是否都计入

测试时至少覆盖单元素、全部相等、严格递增/递减、恰好卡在边界、局部最优容易误导的反例。若无法写出交换论证或领先性质，应暂停使用贪心，转而尝试动态规划、搜索或数据结构。

八、常见误区与追问

误区：总油非负就能从任意站出发。 只保证至少存在某个可行起点。
误区：tank 为负只排除当前起点。 旧起点到失败点之间所有站都不可行。
误区：重置 tank 会丢失总量信息。 total 单独累计全局可行性。
追问：为什么最终 start 可行？ 所有失败前缀已排除且全局总差非负。
追问：若总差为负怎么办？ 无论从哪里开始，绕一圈后都缺油。
追问：如何找所有可行起点？ 单个贪心候选不够，需要进一步前缀和分析。

九、加强记忆

加油站 = 一趟贪心扫描：净油 diff[i]=gas[i]-cost[i]。用 total 累加全程净油——total<0 无解；用 tank 从候选 start 累加，一旦 tank<0 说明 [start,i] 内任何站都当不了起点，start 直接跳到 i+1、tank 清零（因为 start 到中间站油量一直有富余，换更靠后的起点只会更差）。total>=0 时最终的 start 即唯一答案。O(n) 一趟、O(1) 空间。核心两句话：总量定有无解，跳跃定起点。

简化版

详细版