难度: Medium
Submission
运行时间: 38 ms
内存: 26.4 MB
class Solution:
def minimumHealth(self, damage: List[int], armor: int) -> int:
return sum(damage) + 1 - min(max(damage), armor)
Explain
题解的思路是先计算总的伤害值，然后计算最大的单次伤害与护甲值中的较小者，用这个值来减少总伤害的影响。即，我们可以使用护甲值来抵消一次最大的伤害，但护甲值不能超过这次伤害。然后，至少需要总伤害值加1的生命值来通过游戏，再减去护甲能抵消的伤害值。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def minimumHealth(self, damage: List[int], armor: int) -> int:
# 计算所有伤害值的总和
total_damage = sum(damage)
# 找出最大的单次伤害值
max_damage = max(damage)
# 计算护甲可以抵消的伤害（不能超过最大伤害）
armor_effect = min(max_damage, armor)
# 计算通关游戏所需的最低生命值
return total_damage + 1 - armor_effect
Explore
当伤害数组为空时，意味着没有任何伤害。在这种情况下，`total_damage`为0，`max_damage`不存在，但可以认定为0因为没有伤害。因此，`armor_effect`也为0（护甲没有伤害可以抵消）。计算公式变为`0 + 1 - 0`，即至少需要1点生命值来通过游戏。这保证了玩家在没有任何伤害的情况下仍然需要至少1点生命值来存活。
该解法只允许护甲抵消最大的一次伤害值，因为这样做简化了计算过程，同时在许多情况下提供了足够的优化。如果尝试分配护甲值去抵消多个较小的伤害，将需要更复杂的逻辑来确定最优的护甲使用策略。此外，考虑到护甲的最佳用途通常是减少单次最大的伤害，这种简化在大多数情况下是有效且实用的。
确实，如果伤害数组中的值非常大，总伤害值`total_damage`有可能超过Python默认的int类型所能表示的范围。不过，Python的int类型是动态大小的，可以扩展以存储非常大的整数。然而，在其他编程语言中，如C++或Java，这种情况可能导致整数溢出，因此在这些语言中实现时需要特别注意处理大数加法。
在这个算法中，加1代表的是玩家至少需要1点生命值来进入游戏并成功通关，即使总伤害为0。这个1点生命值确保即使在没有任何伤害的情况下，玩家仍然是‘活着’的状态。这是游戏规则的一部分，通常在任何生存游戏中玩家都需要至少1点生命值来维持生存状态。