LeetCode 题解工作台
与敌人战斗后的最大分数
给你一个下标从 0 开始的整数数组 enemyEnergies ，它表示一个下标从 0 开始的敌人能量数组。 同时给你一个整数 currentEnergy ，它表示你一开始拥有的能量值总量。 你一开始的分数为 0 ，且一开始所有的敌人都未标记。 你可以通过以下操作 之一 任意次 （也可以 0 次）来…
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
根据题目描述，我们每次需要通过具有最小能量值的敌人来获得分数，通过具有最大能量值的敌人来增加能量值并进行标记。 因此，我们可以对敌人的能量值进行排序，然后从能量值最大的敌人开始，每次都选择能量值最小的敌人来获得分数，并消耗能量值。然后，我们将能量值最大的敌人的能量值加到当前能量值上，并标记该敌人。重复上述操作，直到所有敌人都被标记。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个下标从 0 开始的整数数组 enemyEnergies ，它表示一个下标从 0 开始的敌人能量数组。
同时给你一个整数 currentEnergy ，它表示你一开始拥有的能量值总量。
你一开始的分数为 0 ，且一开始所有的敌人都未标记。
你可以通过以下操作 之一 任意次（也可以 0 次）来得分：
- 选择一个 未标记 且满足
currentEnergy >= enemyEnergies[i]的敌人i。在这个操作中：- 你会获得
1分。 - 你的能量值减少
enemyEnergies[i]，也就是说currentEnergy = currentEnergy - enemyEnergies[i]。
- 你会获得
- 如果你目前 至少 有
1分，你可以选择一个 未标记 的敌人i。在这个操作中：- 你的能量值增加
enemyEnergies[i]，也就是说currentEnergy = currentEnergy + enemyEnergies[i]。 - 敌人
i被标记 。
- 你的能量值增加
请你返回通过以上操作，最多 可以获得多少分。
示例 1：
输入：enemyEnergies = [3,2,2], currentEnergy = 2
输出：3
解释：
通过以下操作可以得到最大得分 3 分：
- 对敌人 1 使用第一种操作：
points增加 1 ，currentEnergy减少 2 。所以points = 1且currentEnergy = 0。 - 对敌人 0 使用第二种操作：
currentEnergy增加 3 ，敌人 0 被标记。所以points = 1，currentEnergy = 3，被标记的敌人包括[0]。 - 对敌人 2 使用第一种操作：
points增加 1 ，currentEnergy减少 2 。所以points = 2且currentEnergy = 1，被标记的敌人包括[0]。 - 对敌人 2 使用第二种操作：
currentEnergy增加 2 ，敌人 2 被标记。所以points = 2，currentEnergy = 3且被标记的敌人包括[0, 2]。 - 对敌人 1 使用第一种操作：
points增加 1 ，currentEnergy减少 2 。所以points = 3，currentEnergy = 1，被标记的敌人包括[0, 2]。
示例 2：
输入：enemyEnergies = [2], currentEnergy = 10
输出：5
解释：
通过对敌人 0 进行第一种操作 5 次，得到最大得分。
提示：
1 <= enemyEnergies.length <= 1051 <= enemyEnergies[i] <= 1090 <= currentEnergy <= 109
解题思路
方法一：贪心 + 排序
根据题目描述，我们每次需要通过具有最小能量值的敌人来获得分数，通过具有最大能量值的敌人来增加能量值并进行标记。
因此，我们可以对敌人的能量值进行排序，然后从能量值最大的敌人开始，每次都选择能量值最小的敌人来获得分数，并消耗能量值。然后，我们将能量值最大的敌人的能量值加到当前能量值上，并标记该敌人。重复上述操作，直到所有敌人都被标记。
时间复杂度 ，空间复杂度 。其中 是敌人的数量。
class Solution:
def maximumPoints(self, enemyEnergies: List[int], currentEnergy: int) -> int:
enemyEnergies.sort()
if currentEnergy < enemyEnergies[0]:
return 0
ans = 0
for i in range(len(enemyEnergies) - 1, -1, -1):
ans += currentEnergy // enemyEnergies[0]
currentEnergy %= enemyEnergies[0]
currentEnergy += enemyEnergies[i]
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ability to identify the greedy approach and its applicability to the problem.
- question_mark
Understanding of invariant validation and why it’s necessary for maintaining the greedy approach’s correctness.
- question_mark
Efficient handling of edge cases where currentEnergy is too small to defeat any enemies.
常见陷阱
外企场景- error
Failing to sort the enemyEnergies array before starting the battle sequence, which could lead to suboptimal choices.
- error
Not handling the case where the currentEnergy is insufficient to defeat any enemy, which may cause an infinite loop or incorrect results.
- error
Overcomplicating the approach with unnecessary checks or calculations that do not contribute to the greedy choice strategy.
进阶变体
外企场景- arrow_right_alt
Change the array to include enemies with varying point rewards, introducing a new layer of complexity to the greedy choice strategy.
- arrow_right_alt
Introduce multiple energy pools that can be used across different rounds of battles, requiring the management of energy distribution.
- arrow_right_alt
Modify the problem to include a time-based factor where enemies regenerate energy after each round, adding a dynamic element to the greedy approach.