Meta 往返机票最低价：严格日期与索引并列规则

题目重点：给出去程与返程每日价格，要求返程严格晚于出发，在线性时间找最低总价并返回日期下标。

题意与假设

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

D和R等长，下标表示同一日期轴；可用日期都已列出。只能i<j，不能同一天往返。少于两天返回None。
示例并列规则为最早出发，再最晚返程；若题面只要求任意一对，删掉并列规则即可，不改变核心解法。价格可为任意整数；不做实际交易。

解题路线

枚举返程j时，合法去程只在[0,j)；维护此前最小D与对应最早下标。先纳入j−1，再用该去程与R[j]形成候选，保证日期合法。
比较候选用(cost,departureIndex,−returnIndex)，解释负号使更晚返程排前。同一天内最低去程若有同价，保留最早下标才能满足整体并列要求。
不必建立suffixMin或保存所有组合；仅保存当前最低去程与最佳结果即可O(1)辅助空间。若要输出全部最优pair，输出规模本身可能O(n²)。

手动走一遍

D=[10,7,8,3,6]，R=[5,4,10,7,5]，最佳是出发3/返程4，总价8。D=[2,2,9]、R=[8,3,3]，同价最佳应返回(5,0,2)，保留最早出发与最晚返程。

Python 参考实现

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

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

def cheapest_round_trip(departure, returns):
    """Return (cost, departure_index, return_index), earliest departure/latest return ties."""
    if len(departure) != len(returns):
        raise ValueError("aligned date arrays required")
    best = None
    cheapest = None
    for j in range(1, len(returns)):
        i = j - 1
        candidate = (departure[i], i)
        if cheapest is None or candidate < cheapest:
            cheapest = candidate
        price, i = cheapest
        result = (price + returns[j], i, j)
        if best is None or (result[0], result[1], -result[2]) < (best[0], best[1], -best[2]):
            best = result
    return best

复杂度

O(n)时间，O(1)辅助空间；输入不排序不修改。固定宽度整数需保证两个价格求和不溢出。

易错点与追问

容易失分的边界

先纳入D[j]再查询会允许同日往返；合法前缀必须截止j−1。
只比较价格、不更新并列日期，会返回错误索引；去程最小值同价也要一致。

继续深挖

若需要至少住k晚，将候选去程纳入位置改为j−k。若价格缺失，用不可用标记跳过，不能假设缺失价为0。
若去程和返程分别有不同日期列表，双指针按日期纳入严格更早的出发，而非比较数组下标。