算法题求解：计算满足返程不早于出发要求的最低往返机票费用

最优解法思路 #

这道题的暴力解法时间复杂度为O(n²)，我们可以通过动态维护合法区间极值的方式把复杂度降到O(n)，空间复杂度优化到O(1)。
核心逻辑：我们需要找所有满足返程下标j >= 出发下标i的组合D[i] + R[j]的最小值。对于任意一个返程下标j，所有下标<=j的出发航班都符合时间要求，因此我们只需要在遍历到j的时候，维护从起点到j位置的D数组最小值，就能直接算出当前j对应的最低出发成本，加上当前R[j]的值就是当前j对应的最低往返成本，遍历所有j取全局最小值即可。

示例推导过程 #

以题目给出的输入为例：

D = [10,7,13,12,4]
R = [5,12,7,10,12]

• j=0：D的最小值为10，总费用10+5=15，当前全局最小15
• j=1：D的最小值更新为7，总费用7+12=19，全局最小保持15
• j=2：D的最小值保持7，总费用7+7=14，全局最小更新为14
• j=3：D的最小值保持7，总费用7+10=17，全局最小保持14
• j=4：D的最小值更新为4，总费用4+12=16，全局最小保持14
  最终结果为14，和题目给出的示例结果一致。

代码实现 #

def min_round_trip_cost(D, R):
    if not D or len(D) != len(R):
        return 0
    min_d = float('inf')
    min_total = float('inf')
    for j in range(len(D)):
        # 更新到当前位置的最低出发票价
        min_d = min(min_d, D[j])
        min_total = min(min_total, min_d + R[j])
    return min_total

如果需要固定出发时间来计算，也可以选择从右往左遍历，维护从当前位置到末尾的最低返程票价，计算逻辑完全一致：

def min_round_trip_cost(D, R):
    if not D or len(D) != len(R):
        return 0
    min_r = float('inf')
    min_total = float('inf')
    for i in range(len(D)-1, -1, -1):
        min_r = min(min_r, R[i])
        min_total = min(min_total, D[i] + min_r)
    return min_total

同类问题通用优化思路 #

所有带单向下标范围约束的极值求解问题，都可以用这个思路优化：

• 先明确约束的范围关系，比如本题是返程下标大于等于出发下标，合法范围是单向扩展的
• 遍历过程中动态维护当前合法范围内的极值（最大/最小值），不需要每次重新扫描整个区间
• 可以直接把O(n²)的暴力解法降为O(n)线性时间复杂度，多数场景下可以做到O(1)额外空间

内容的提问来源于stack exchange，提问作者zvonimir