2008. 出租车的最大盈利

发表于 2026-01-12 分类于力扣阅读次数： Waline：本文字数： 1.1k 阅读时长 ≈ 4 分钟

考点

划分DP
线性DP

思路

一、问题概述

给定一条从位置 \(1\) 到位置 \(n\) 的一维道路，以及若干笔出租车订单。每一笔订单由三元组 \((s, e, t)\) 表示：

\(s\)：乘客上车位置
\(e\)：乘客下车位置
\(t\)：额外小费

司机从 \(1\) 出发，沿着道路单向前进，可以选择是否接某些订单。 约束条件：

一旦接单，必须从 \(s\) 行驶到 \(e\)，期间不能接其他订单
行驶的基础收益为路程长度 \(e - s\)，总收益为 \[ (e - s) + t \]

目标：在合理选择订单的前提下，最大化总收益。

二、问题建模思路

这是一个典型的 区间选择 + 最优收益累积 问题，其核心特征是：

时间（或位置）是单调递增的
每一笔订单在一个确定的终点 \(e\) 结束
在位置 \(e\) 的最优决策，依赖于某个更早位置 \(s\)

这类问题非常适合使用 一维动态规划（DP） 建模。

三、动态规划状态设计

1. 状态定义

定义一维 DP 数组： \[ f[i] = \text{到达位置 } i \text{ 时可以获得的最大收益} \] 其中 \(i \in [0, n]\)，并约定： \[ f[0] = 0 \]

2. 状态含义解释

\(f[i]\) 并不意味着“必须在 \(i\) 接单或下车”
它表示：司机已经行驶到位置 \(i\)，在此前的所有决策中所能取得的最大收益
在位置 \(i\)，司机可以选择：
- 什么都不做，继续前进
- 在这里完成某一笔订单

四、状态转移方程设计

在位置 \(i\)，有两种决策来源：

情况一：不接任何在 \(i\) 结束的订单

司机从 \(i-1\) 行驶到 \(i\)，不产生额外收益： \[ f[i] = f[i-1] \]

情况二：接一笔在 \(i\) 结束的订单

设存在订单 \((s, i, t)\)，则该订单的收益为： \[ (i - s) + t \] 若司机在 \(s\) 之前已经获得最大收益 \(f[s]\)，那么完成该订单后的总收益为： \[ f[s] + (i - s) + t \] 因此可以更新： \[ f[i] = \max\left(f[i],\ f[s] + i - s + t\right) \]

综合状态转移

将两种情况合并，得到完整转移方程： \[ f[i] = \max \Bigg( f[i-1],\ \max_{(s,i,t)\in \text{rides}} \bigl(f[s] + i - s + t\bigr) \Bigg) \]

五、订单组织方式的优化

为了高效实现上述转移，需要避免在每个 \(i\) 上遍历所有订单。

常用技巧是：

按订单终点分组
预处理一个数组 ends，其中：

\[ \text{ends}[i] = \{(s, t) \mid \exists\ (s, i, t)\} \]

这样，在计算 \(f[i]\) 时，只需遍历 ends[i] 中的订单即可。

六、算法流程总结

按终点将所有订单分组
初始化 DP 数组，令 \(f[0] = 0\)
从 \(i = 1\) 到 \(n\) 顺序计算：
- 先继承：\(f[i] = f[i-1]\)
- 枚举所有在 \(i\) 结束的订单，尝试更新 \(f[i]\)
最终答案为 \(f[n]\)

七、时间与空间复杂度分析

时间复杂度： \[ O(n + \text{rides.size()}) \] 每个位置只处理一次，每个订单只被访问一次。
空间复杂度： \[ O(n + \text{rides.size()}) \]

八、AC代码

class Solution {
public:
    // 最大位置上界，题目约束 n <= 1e5
    static const int maxn = 1e5 + 5;

    long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {
        // ends[i]：所有终点为 i 的订单
        // pair<int, int> 表示 (起点 s, 小费 t)
        vector<vector<pair<int, int>>> ends(n + 1);

        // 将订单按终点分组
        for (auto& ride : rides) {
            int s = ride[0];
            int e = ride[1];
            int t = ride[2];
            ends[e].push_back({s, t});
        }

        // f[i]：到达位置 i 时的最大收益
        long long f[maxn];

        // 起点收益为 0
        f[0] = 0;

        // 依次计算 f[1] 到 f[n]
        for (int i = 1; i <= n; ++i) {
            // 情况一：不接任何在 i 结束的订单
            f[i] = f[i - 1];

            // 情况二：接一笔在 i 结束的订单
            for (auto& [s, t] : ends[i]) {
                // 收益 = f[s] + (i - s) + t
                f[i] = max(f[i], f[s] + i - s + t);
            }
        }

        // 返回到达 n 的最大收益
        return f[n];
    }
};