Uber 往返机票最低价：返程必须晚于出发日

题意与假设

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

• A[i] 和 B[i] 分别是第 i 天的出发票价与返程票价，长度相同；可任选出发日 i 与返程日 j，但 j≥i+min_gap。
• 原题严格晚于意味着 min_gap=1；题目追问至少隔 3 天可令 min_gap=3。日期下标从 0 开始，返回最低总价及对应日期，若无合法组合返回 None。
• 价格按整数表示；同价时示例取最早出发日、再取最早返程日，真实题若只要价格可省去破平局规则。

解题路线

1. 从右向左预处理 suffix_day[d]：在日期 d..n−1 中返程价最低的日期，同价取更早日期。
2. 对每个可行出发日 i，只需配上 suffix_day[i+min_gap]，因为这已是在合法返程区间内最便宜的一张票。
3. 在所有出发日候选中选最低 (A[i]+B[j],i,j)。每个合法组合的返程价都不低于其出发日的后缀最小值，所以选优不会漏解。

手动走一遍

A=[1,100]、B=[1,100] 时，若误用 B[i..] 会选第 0 天同日往返得到 2；严格晚于只允许 (0,1)，正确总价 101。若至少隔 3 天，返程查询从 i+3 开始。

Python 参考实现

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

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

"""Cheapest departure/return pair with a minimum day gap."""


def cheapest_round_trip(departures: list[int], returns: list[int], min_gap: int = 1) -> tuple[int, int, int] | None:
    if len(departures) != len(returns) or min_gap < 1:
        raise ValueError("matching day arrays and min_gap >= 1 required")
    n = len(departures)
    if n <= min_gap:
        return None
    suffix_day = [n - 1] * n
    for day in range(n - 2, -1, -1):
        next_day = suffix_day[day + 1]
        suffix_day[day] = day if (returns[day], day) <= (returns[next_day], next_day) else next_day
    best: tuple[int, int, int] | None = None
    for leave in range(n - min_gap):
        come_back = suffix_day[leave + min_gap]
        candidate = (departures[leave] + returns[come_back], leave, come_back)
        if best is None or candidate < best:
            best = candidate
    return best

复杂度

构建返程后缀最优日期与扫描出发日各 O(n)，总时间 O(n)、空间 O(n)。若只需最低价格且不返回日期，也可用从右向左的单个最小 B 值降到 O(1) 辅助空间。

易错点与追问

容易失分的边界

• 题目示意 B[i..n−1] 允许同日返程，与其明确的‘出发日必须早于返程日’矛盾；应从 i+1 起。
• 至少隔 d 天时，最后 d 个出发日没有合法返程，不应越界或复用更早返程。
• 逐日 A 与 B 不能各自独立取全局最低价；两次最低价所在日期可能违反先后顺序。

继续深挖

• 若还有最长停留 D 天，合法返程成为 [i+d,i+D] 范围最小值，可用滑动窗口单调队列或 RMQ。
• 若票价动态更新且频繁查询，静态后缀表需重建；可按日期建线段树做区间最小价查询。