Bloomberg 环形地球燃料点：任选起点最多行驶多少英里

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练版只顺时针前进，初始油量为所选起点的 fuel，每站最多领取一次；油箱无限容量。
• ‘最多行驶多远’指从出发到油尽的累计英里，允许在两个站之间停下；若要最大最终位置或允许掉头，解法不同。
• 站点坐标唯一且在 [0,circumference)，燃料非负；站点排序不代表输入已有序。

解题路线

1. 先按位置排序；枚举每个出发站，带 tank、traveled、current 模拟前进。
2. 下一站的顺时针间隔 = (nextPos-currentPos) mod C；若 tank<gap，就只能再走 tank 英里并停下。
3. 若能到达，扣 gap、加 traveled，再领取该站燃料；只访问最多 n−1 个后续站，避免绕圈回到起点重复加油。
4. 该起点最终行驶距离为 traveled+tank，取所有起点最大。可用前缀和/倍增处理大 n，但需仔细处理无法跨越的首个间隔和一次领取约束。

手动走一遍

第一组从 40 出发先拿 100，能绕过 10、20 各拿 10，最终可用总油 120 英里。第二组从 10 拿 10 到 20，再拿 20；到 41 需 21 英里，油只有 20，于是最终共 30 英里。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def max_circular_fuel_miles(stations, circumference=100):
    """One-time fuel pickups; drive clockwise until fuel runs out."""
    if circumference <= 0:
        raise ValueError("circumference must be positive")
    if not stations:
        return 0
    stations = sorted(stations)
    if len({position for position, _ in stations}) != len(stations):
        raise ValueError("station positions must be unique")
    if any(not (0 <= position < circumference) or fuel < 0 for position, fuel in stations):
        raise ValueError("invalid station")
    n = len(stations)
    answer = 0
    for start in range(n):
        tank = stations[start][1]
        traveled = 0
        current = start
        for _ in range(n - 1):
            following = (current + 1) % n
            gap = (stations[following][0] - stations[current][0]) % circumference
            if tank < gap:
                break
            tank -= gap
            traveled += gap
            tank += stations[following][1]
            current = following
        answer = max(answer, traveled + tank)
    return answer

复杂度

排序 O(n log n)，每个起点最多 n−1 次跳站，时间 O(n²)，额外空间 O(n) 排序副本；n 很大时需优化但题目无规模。

易错点与追问

容易失分的边界

• 到不了下一站时忘记把剩余油计入已行驶距离。
• 第二圈重复领取已经使用过的站。
• 把两站距离当绝对差而漏回绕。
• 未澄清是否可逆向行驶或起点不在燃料站。

继续深挖

• 若可从任意坐标而不只站点出发？
• 若油箱容量有限？
• 若要求 O(n log n) 或更快？
• 若允许逆向或掉头，状态如何变化？