README.md

comments	difficulty	edit_url	tags
true	中等	https://github.com/doocs/leetcode/edit/main/solution/2200-2299/2214.Minimum%20Health%20to%20Beat%20Game/README.md	贪心 数组

2214. 通关游戏所需的最低生命值 🔒

English Version

题目描述

你正在玩一个有 n 个关卡的游戏，从 0 到 n - 1。给你一个 下标从 0 开始 的整数数组 damage，其中 damage[i] 是你完成第 i 个关卡所损失的生命值。

你也会得到一个整数 armor。你最多只能在 任何 等级使用 一次 护甲技能，这将保护你免受 最多 armor 伤害。

你必须按顺序完成关卡，并且你的生命值必须一直 大于 0 才能通关。

返回你开始通关所需的最低生命值。

 

示例 1:

输入: damage = [2,7,4,3], armor = 4
输出: 13
解释: 从 13 生命值开始通关游戏的最佳方法是:
第 1 回合，受到 2 点伤害。你还有 13 - 2 = 11 生命值。
第 2 回合，受到 7 点伤害。你还有 11 - 7 = 4 生命值。
第 3 回合，使用你的护甲保护你免受 4 点伤害。你有 4 - 0 = 4 生命值。
第 4 回合，受到 3 点伤害。你还有 4 - 3 = 1 生命值。
注意，13 是你开始时通关游戏所需的最低生命值。

示例 2:

输入: damage = [2,5,3,4], armor = 7
输出: 10
解释: 从 10 生命值开始通关游戏的最佳方法是:
第 1 回合，受到 2 点伤害。你还有 10 - 2 = 8 生命值。
第 2 回合，使用护甲保护自己免受 5 点伤害。你还有 8 - 0 = 8 生命值。
第 3 回合，受到 3 点伤害。你还有 8 - 3 = 5 生命值。
第 4 回合，受到 4 点伤害。你还有 5 - 4 = 1 生命值。
注意，10 是你开始通关所需的最低生命值。

示例 3:

输入: damage = [3,3,3], armor = 0
输出: 10
解释: 从 10 生命值开始通关游戏的最佳方法是:
第 1 回合，受到 2 点伤害。你还有 10 - 3 = 7 生命值。
第 2 回合，受到 3 点伤害。你还有 7 - 3 = 4 生命值。
第 3 回合， 受到 3 点伤害。你还有 4 - 3 = 1 生命值。
注意你没有使用护甲技能。

 

提示:

• n == damage.length
• 1 <= n <= 105
• 0 <= damage[i] <= 105
• 0 <= armor <= 105

解法

方法一：贪心

我们可以贪心地选择在伤害值最大的回合中使用一次护甲技能，假设伤害值最大为 $mx$，那么我们可以免受 $min(mx, armor)$ 的伤害，因此我们需要的最小生命值为 $sum(damage) - min(mx, armor) + 1$。

时间复杂度 $O(n)$，其中 $n$ 为数组 damage 的长度。空间复杂度 $O(1)$。

Python3

class Solution:
    def minimumHealth(self, damage: List[int], armor: int) -> int:
        return sum(damage) - min(max(damage), armor) + 1

Java

class Solution {
    public long minimumHealth(int[] damage, int armor) {
        long s = 0;
        int mx = damage[0];
        for (int v : damage) {
            s += v;
            mx = Math.max(mx, v);
        }
        return s - Math.min(mx, armor) + 1;
    }
}

C++

class Solution {
public:
    long long minimumHealth(vector<int>& damage, int armor) {
        long long s = 0;
        int mx = damage[0];
        for (int& v : damage) {
            s += v;
            mx = max(mx, v);
        }
        return s - min(mx, armor) + 1;
    }
};

Go

func minimumHealth(damage []int, armor int) int64 {
	var s int64
	var mx int
	for _, v := range damage {
		s += int64(v)
		mx = max(mx, v)
	}
	return s - int64(min(mx, armor)) + 1
}

TypeScript

function minimumHealth(damage: number[], armor: number): number {
    let s = 0;
    let mx = 0;
    for (const v of damage) {
        mx = Math.max(mx, v);
        s += v;
    }
    return s - Math.min(mx, armor) + 1;
}