class Solution {
public:
vector<long long> maximumCoins(vector<int>& heroes, vector<int>& monsters, vector<int>& coins) {
}
};
2838. Maximum Coins Heroes Can Collect
There is a battle and n heroes are trying to defeat m monsters. You are given two 1-indexed arrays of positive integers heroes and monsters of length n and m, respectively. heroes[i] is the power of ith hero, and monsters[i] is the power of ith monster.
The ith hero can defeat the jth monster if monsters[j] <= heroes[i].
You are also given a 1-indexed array coins of length m consisting of positive integers. coins[i] is the number of coins that each hero earns after defeating the ith monster.
Return an array ans of length n where ans[i] is the maximum number of coins that the ith hero can collect from this battle.
Notes
Example 1:
Input: heroes = [1,4,2], monsters = [1,1,5,2,3], coins = [2,3,4,5,6] Output: [5,16,10] Explanation: For each hero, we list the index of all the monsters he can defeat: 1st hero: [1,2] since the power of this hero is 1 and monsters[1], monsters[2] <= 1. So this hero collects coins[1] + coins[2] = 5 coins. 2nd hero: [1,2,4,5] since the power of this hero is 4 and monsters[1], monsters[2], monsters[4], monsters[5] <= 4. So this hero collects coins[1] + coins[2] + coins[4] + coins[5] = 16 coins. 3rd hero: [1,2,4] since the power of this hero is 2 and monsters[1], monsters[2], monsters[4] <= 2. So this hero collects coins[1] + coins[2] + coins[4] = 10 coins. So the answer would be [5,16,10].
Example 2:
Input: heroes = [5], monsters = [2,3,1,2], coins = [10,6,5,2] Output: [23] Explanation: This hero can defeat all the monsters since monsters[i] <= 5. So he collects all of the coins: coins[1] + coins[2] + coins[3] + coins[4] = 23, and the answer would be [23].
Example 3:
Input: heroes = [4,4], monsters = [5,7,8], coins = [1,1,1] Output: [0,0] Explanation: In this example, no hero can defeat a monster. So the answer would be [0,0],
Constraints:
1 <= n == heroes.length <= 1051 <= m == monsters.length <= 105coins.length == m1 <= heroes[i], monsters[i], coins[i] <= 109原站题解
python3 解法, 执行用时: 360 ms, 内存消耗: 37 MB, 提交时间: 2023-10-15 18:04:47
class Solution:
def maximumCoins(self, heroes: List[int], monsters: List[int], coins: List[int]) -> List[int]:
monsters, coins = zip(*sorted(zip(monsters, coins)))
lst = [(0, 0)] + list(zip(monsters, accumulate(coins)))
return [lst[bisect_right(lst, (x, inf)) - 1][1] for x in heroes]
golang 解法, 执行用时: 180 ms, 内存消耗: 14.1 MB, 提交时间: 2023-10-15 18:04:24
func maximumCoins(heroes []int, monsters []int, coins []int) []int64 {
var arr [][]int
for i := 0; i < len(monsters); i++ {
arr = append(arr, []int{monsters[i], coins[i]})
}
sort.Slice(arr, func(i, j int) bool {
return arr[i][0] <= arr[j][0]
})
preArr := make([]int, len(arr))
for i := 0; i < len(preArr); i++ {
preArr[i] = arr[i][1]
if i != 0 {
preArr[i] += preArr[i-1]
}
}
res := make([]int64, len(heroes))
for i := 0; i < len(res); i++ {
index := leetcode2838testGetIndex(arr, heroes[i])
if index != 0 {
res[i] = int64(preArr[index-1])
}
}
return res
}
func leetcode2838testGetIndex(arr [][]int, n int) int {
if len(arr) <= 4 {
for i := 0; i < len(arr); i++ {
if arr[i][0] > n {
return i
}
}
return len(arr)
}
return leetcode2838testErfen(arr, 0, len(arr)-1, n)
}
func leetcode2838testErfen(arr [][]int, low, high, n int) int {
mid := (low + high) / 2
if mid == 0 || mid == len(arr)-1 {
if arr[mid][0] > n {
return mid
}
return mid + 1
}
f1, f2 := arr[mid][0] > n, arr[mid-1][0] <= n
if f1 && f2 {
return mid
}
if f1 {
return leetcode2838testErfen(arr, low, mid-1, n)
}
return leetcode2838testErfen(arr, mid+1, high, n)
}