出租车的最大盈利

标签: 数组 哈希表 二分查找 动态规划 排序

难度: Medium

你驾驶出租车行驶在一条有 n 个地点的路上。这 n 个地点从近到远编号为 1 到 n ，你想要从 1 开到 n ，通过接乘客订单盈利。你只能沿着编号递增的方向前进，不能改变方向。

乘客信息用一个下标从 0 开始的二维数组 rides 表示，其中 rides[i] = [starti, endi, tipi] 表示第 i 位乘客需要从地点 starti 前往 endi ，愿意支付 tipi 元的小费。

每一位 你选择接单的乘客 i ，你可以 盈利 endi - starti + tipi 元。你同时 最多 只能接一个订单。

给你 n 和 rides ，请你返回在最优接单方案下，你能盈利 最多 多少元。

注意：你可以在一个地点放下一位乘客，并在同一个地点接上另一位乘客。

示例 1：

输入：n = 5, rides = [[2,5,4],[1,5,1]]
输出：7
解释：我们可以接乘客 0 的订单，获得 5 - 2 + 4 = 7 元。

示例 2：

输入：n = 20, rides = [[1,6,1],[3,10,2],[10,12,3],[11,12,2],[12,15,2],[13,18,1]]
输出：20
解释：我们可以接以下乘客的订单：
- 将乘客 1 从地点 3 送往地点 10 ，获得 10 - 3 + 2 = 9 元。
- 将乘客 2 从地点 10 送往地点 12 ，获得 12 - 10 + 3 = 5 元。
- 将乘客 5 从地点 13 送往地点 18 ，获得 18 - 13 + 1 = 6 元。
我们总共获得 9 + 5 + 6 = 20 元。

提示：

  • 1 <= n <= 105
  • 1 <= rides.length <= 3 * 104
  • rides[i].length == 3
  • 1 <= starti < endi <= n
  • 1 <= tipi <= 105

Submission

运行时间: 256 ms

内存: 33.5 MB

class Solution:
    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
        dp = [0] * (n + 1)
        rideMap = {}
        for ride in rides:
            if ride[1] not in rideMap:
                rideMap[ride[1]] = []
            rideMap[ride[1]].append(ride)
        for i in range(1,n+1):
            dp[i] = dp[i-1]
            if i not in rideMap:
                continue
            for ride in rideMap[i]:
                dp[i] = max(dp[i],dp[ride[0]]+ride[1]-ride[0]+ride[2])
        return dp[n]

Explain

本题解采用动态规划的方法解决问题。定义 dp[i] 为到达第 i 个地点时能获得的最大盈利。对于每个地点 i，首先保持 dp[i] 等于 dp[i-1]（即不接新的乘客情况下的盈利），然后检查是否有乘客在此地点结束行程。如果有，则尝试接该乘客并计算接此乘客所能获得的盈利（包括行程费和小费），并更新 dp[i]。对于每个结束点 i，查看所有在此结束的行程，计算如果接此乘客从他们的起始点 start 到 i 所能得到的盈利，更新 dp[i] 为最大值。最终，dp[n] 将是从 1 到 n 地点能获得的最大盈利。

时间复杂度: O(n + m)

空间复杂度: O(n + m)

class Solution:
    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
        dp = [0] * (n + 1)  # 动态规划数组，dp[i] 表示到达第 i 个地点时能获得的最大盈利
        rideMap = {}  # 存储以各个地点为结束点的乘客信息
        for ride in rides:
            if ride[1] not in rideMap:
                rideMap[ride[1]] = []
            rideMap[ride[1]].append(ride)
        for i in range(1, n+1):
            dp[i] = dp[i-1]  # 初始假设在地点 i 的盈利与地点 i-1 相同
            if i in rideMap:
                for ride in rideMap[i]:
                    profit = dp[ride[0]] + ride[1] - ride[0] + ride[2]  # 计算接当前乘客的总盈利
                    dp[i] = max(dp[i], profit)  # 选择最优盈利方案
        return dp[n]  # 返回最大盈利

Explore

在动态规划中，dp[i]的初始值设置为dp[i-1]是为了保持前一个地点的最大盈利。这样的初始化假设在地点i没有接新的乘客，因此盈利与前一个地点i-1相同。这一步骤确保了dp数组能够传递不接客时的盈利状态，保证dp[i]总是反映到达第i个地点时可能的最大盈利。若选择其他值如0，可能会丢失前面地点积累的盈利信息。

乘客信息通过一个字典rideMap存储，其中每个结束地点作为键，值则是一个列表，包含所有在该地点结束的乘客的起始点、结束点和小费信息的列表。这种存储方式允许快速访问以任何特定地点结束的所有行程，当处理到地点i时，可以直接通过rideMap[i]获取所有在此结束的乘客信息，从而进行盈利计算。这种方法避免了对每个地点重复搜索所有行程，提高了算法的效率。

为了确保选择能够最大化盈利的乘客，算法在每个结束点i检查所有结束于该点的乘客。对于每个乘客，计算从他们的起始点到结束点的总盈利（包括路程费和小费），然后将这个盈利与当前dp[i]进行比较，取二者中的最大值更新dp[i]。这样，dp[i]总是存储到达第i个地点时可能的最大盈利，确保了在多个选项中总是选择最佳的盈利方案。

在动态规划解法中，选择只考虑当前结束点的乘客而不是所有可能的乘客组合，是因为动态规划的优化目标是简化问题并避免冗余计算。通过之前的状态（dp[ride[0]]）和当前乘客信息计算当前状态（dp[i]），我们已经隐式地考虑了从起点到当前点的所有最优乘客组合。如果尝试在每个点考虑所有可能的乘客组合，将会导致时间复杂度过高，而动态规划正是为了避免这种复杂度爆炸，并确保每一步计算都是基于之前计算的最优解。