加油站

周子力大约 6 分钟教学文档贪心算法

题目描述

解题思路

好的，这是一个经典的贪心算法问题，它巧妙地结合了数学上的“净收益”概念。

求解思路：

问题转换：首先，我们计算每个加油站的“净收益” net_gain[i] = gas[i] - cost[i]。这表示从第 i 个加油站出发，到达下一个加油站后，油箱里净增加或净减少的油量。
总体可行性判断：如果所有 net_gain 的总和 sum(net_gain) 小于 0，这意味着整个环路的总耗油量大于总加油量，无论从哪里出发都无法完成一圈。因此，如果 sum(gas) < sum(cost)，直接返回 -1。
寻找起点：如果总油量是足够的，那么必然存在一个起点。关键在于如何找到它。
- 贪心策略：我们从索引 0 开始，模拟行驶过程，并维护一个变量 current_tank 来记录当前油箱里的油量。
- 何时重新开始：如果在某个点 i，current_tank 变成了负数，这意味着从我们之前选择的起点（比如 start）出发，无法到达点 i。这说明 start 到 i-1 中的任何一个点都不可能是正确的起点。为什么？因为从 start 出发都无法到达 i，那么从 start 和 i 之间的任何一点出发，油量只会更少，更不可能到达 i。
- 更新起点：因此，当 current_tank 变为负数时，我们可以贪心地将起点更新为 i+1，并重新开始计算 current_tank。
- 为什么这个策略是正确的？
  - 我们已经知道总油量是足够的。
  - 当 current_tank 在点 i 变为负数时，意味着从 start 到 i 这一段路径的净消耗是负的（即 sum(net_gain[start:i+1]) < 0）。
  - 由于总净收益是正的，那么剩下的那一段路径（从 i+1 到 start-1，如果 start > 0，否则是 i+1 到末尾再绕回来）的净收益必须是正的，并且足以弥补前面的亏损。
  - 因此，从 i+1 这个点开始，油箱里的油量在绕行一圈的过程中不会变为负数，它就是一个有效的起点。

Python 代码实现：

def canCompleteCircuit(gas, cost):
    """
    :param gas: List[int] - 每个加油站的加油量
    :param cost: List[int] - 从每个加油站开往下一个加油站的耗油量
    :return: int - 能够完成环路一周的起始加油站索引，如果不存在则返回 -1
    """
    total_gas = sum(gas)
    total_cost = sum(cost)

    # 1. 如果总油量小于总耗油量，不可能完成环路
    if total_gas < total_cost:
        return -1

    n = len(gas)
    current_tank = 0  # 当前油箱里的油量
    start_station = 0 # 假设的起始加油站索引

    # 2. 遍历所有加油站，寻找合适的起点
    for i in range(n):
        # 计算从当前加油站出发，到达下一站后的净油量变化
        net_gain = gas[i] - cost[i]
        current_tank += net_gain

        # 3. 如果油箱里的油不够了，说明从 start_station 出发无法到达 i+1 站
        # 因此，将起点更新为 i+1，并重置油箱
        if current_tank < 0:
            start_station = i + 1
            current_tank = 0

    # 4. 如果循环结束，说明从 start_station 出发可以走完一圈
    # （因为我们已经通过了总油量检查，所以这个 start_station 一定是正确的）
    return start_station

# --- 示例测试 ---
# 示例 1
gas1 = [1, 2, 3, 4, 5]
cost1 = [3, 4, 5, 1, 2]
print(f"输入: gas = {gas1}, cost = {cost1}")
print(f"输出: {canCompleteCircuit(gas1, cost1)}")  # 输出: 3

# 示例 2
gas2 = [2, 3, 4]
cost2 = [3, 4, 3]
print(f"输入: gas = {gas2}, cost = {cost2}")
print(f"输出: {canCompleteCircuit(gas2, cost2)}")  # 输出: -1

加油站问题：注意事项与启发

1. 问题转化的关键：净收益

核心启发：将原始的 gas[i]（加油）和 cost[i]（耗油）两个数组，转化为一个 net_gain[i] = gas[i] - cost[i] 的数组，是解决这个问题的关键一步。这个转化将“加油”和“耗油”两个动作合并成一个“净变化”动作，极大地简化了问题的复杂度。我们不再需要同时跟踪加油和耗油两个变量，只需要关注油箱里的油量是增加还是减少。
注意：在编写代码时，不需要显式地创建 net_gain 数组，而是在遍历时直接计算 gas[i] - cost[i]，这样可以节省空间。

2. 全局可行性检查

重要前提：在进行局部搜索之前，必须首先判断全局上是否存在解。如果 sum(gas) < sum(cost)，则总油量不足以完成一圈，直接返回 -1。这是算法正确性的基础。
启发：在解决优化或路径问题时，先进行一个快速的可行性检查，可以避免不必要的复杂计算，提高算法效率。

3. 贪心策略的正确性证明

核心策略：当 current_tank 变为负数时，将起点更新为当前位置的下一个点。这个看似简单的操作，其正确性是基于一个重要的逻辑：如果从点 A 无法到达点 B，那么从 A 和 B 之间的任何一点出发，也必然无法到达 B。因为从 A 出发时，初始油量为 0，而从 A 和 B 之间的点出发时，初始油量（从 A 到该点的累积油量）可能为正也可能为负，但其到达 B 的路径更短，如果 A 都到不了 B，那么更短路径的点也到不了。
注意：理解这个“贪心跳跃”的逻辑是掌握此算法的核心。它不是随机跳跃，而是基于逻辑推理的必然选择。

4. 变量的精确含义

current_tank：这个变量的含义是从当前假设的起点 start_station 开始，行驶到当前位置 i 时，油箱里剩余的油量。它不是从 0 点开始的总油量。
start_station：这个变量是当前正在尝试的、可能正确的起点。它会随着 current_tank 变为负数而更新。
注意：在代码实现中，current_tank 的更新是累加的，它会自动包含从 start_station 到 i 的所有净收益。当它变为负数时，就证明了 start_station 不可行。

5. 循环不变式 (Loop Invariant)

启发：可以将算法看作一个循环不变式：在每次循环开始前，start_station 是当前找到的、可能有效的起点，且从 start_station 到 i-1 的所有净收益之和 current_tank 都是非负的。
注意：理解循环不变式有助于验证算法的正确性。

6. 唯一解的保证

题目条件：题目明确指出“如果存在解，则保证它是唯一的”。这保证了我们的贪心策略在找到第一个可行起点后，无需再继续搜索其他可能的起点。
注意：如果题目没有这个保证，问题的复杂度会大大增加。

7. 启发

贪心算法的应用：这个问题展示了贪心算法如何通过“局部最优决策”来构建全局解。其“跳跃”策略避免了对每个点都进行完整的模拟，时间复杂度仅为 $O(N)$ 。
转化与抽象：将问题抽象成一个更简单的数学模型（净收益）是解决问题的关键。这在很多算法题中都是一种重要的思维方式。
逻辑推理的重要性：算法的正确性依赖于严谨的逻辑推理。理解“为什么可以跳过中间点”比记住代码本身更重要。
状态变量的设计：current_tank 和 start_station 的设计非常巧妙，它们共同维护了算法运行时的状态，使得我们可以在一次遍历中完成任务。