难度: Medium
Submission
运行时间: 244 ms
内存: 34.4 MB
class Solution:
def maximumCoins(self, heroes: List[int], monsters: List[int], coins: List[int]) -> List[int]:
n, m = len(heroes), len(monsters)
idxH = sorted(range(n), key=lambda x : heroes[x])
idxM = sorted(range(m), key=lambda x : monsters[x])
res = [0] * n
cur = j = 0
for i in idxH:
while j < m and monsters[idxM[j]] <= heroes[i]:
cur += coins[idxM[j]]
j += 1
res[i] = cur
return res
Explain
该题解采用了排序和双指针的策略。首先对英雄和怪物的能力值进行排序，并记录原始索引。接着使用双指针技术，一个指针遍历英雄列表，另一个指针遍历怪物列表。当怪物的能力值小于或等于当前英雄的能力值时，累加对应的金币数。这样可以确保每个英雄能够计算出他们能够战胜的所有怪物的总金币数。
时间复杂度: O(n log n + m log m)
空间复杂度: O(n + m)
class Solution:
def maximumCoins(self, heroes: List[int], monsters: List[int], coins: List[int]) -> List[int]:
n, m = len(heroes), len(monsters)
# 排序英雄和怪物，记录原始索引
idxH = sorted(range(n), key=lambda x : heroes[x])
idxM = sorted(range(m), key=lambda x : monsters[x])
res = [0] * n # 初始化结果数组
cur = j = 0
# 使用双指针遍历英雄和怪物
for i in idxH:
while j < m and monsters[idxM[j]] <= heroes[i]:
cur += coins[idxM[j]] # 累加金币
j += 1
res[i] = cur # 记录当前英雄可以获得的金币总数
return res
Explore
在排序怪物和英雄列表之前记录它们的原始索引是为了在最终输出结果时能够将计算的金币数正确地分配给相应的英雄。因为排序会改变元素的位置，如果不记录原始索引，那么在给英雄分配他们赢取的金币时，就无法确保这些金币是分给正确的英雄。通过记录索引，算法可以在保持英雄和怪物相对能力顺序的同时，确保输出的结果是按照英雄初始顺序排列的。
在双指针策略中，如果遇到英雄和怪物的能力值相等的情况，该策略会将这个怪物的金币加到当前英雄的总金币中。这是因为根据题目逻辑，英雄能够战胜的怪物包括那些其能力值小于或等于英雄能力值的怪物。因此，当遇到能力值相等时，英雄同样可以战胜这个怪物并获得相应的金币。
双指针策略通过分别设置一个指针遍历英雄列表（按能力值排序后）和一个指针遍历怪物列表（同样按能力值排序后）。英雄指针不回退，怪物指针在满足条件的情况下前进并累积金币到当前英雄，当怪物的能力值超过当前英雄时停止。然后移动到下一个英雄，并从上一次停止的怪物位置继续遍历。这样，每个怪物只会被计算一次，确保了金币的计算不会重复，也不会遗漏任何一个怪物。
`cur`变量在算法中用于累积当前英雄可以获得的金币总数。当算法使用双指针遍历怪物列表时，每遇到一个能被当前英雄战胜的怪物，就将其金币值加到`cur`上。当所有能被当前英雄战胜的怪物都累加完后，`cur`的值就是该英雄能获得的总金币数。接着，算法继续遍历下一个英雄，并从上一个英雄处理完的最后一个怪物开始，继续使用`cur`累积金币。这样，`cur`在不同英雄之间传递，保证了金币的正确累积和计算。