Question

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)$，空间复杂度 $O(1)$。其中 $n$ 为数组 damage 的长度。

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

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;
  }
}

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;
  }
};

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
}

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;
}