Medium

题目描述

给你一个整数数组 enemyEnergies，表示各个敌人的能量值。

同时给你一个整数 currentEnergy，表示你初始拥有的能量。

你从 0 分开始，所有敌人最初都是未标记的。

你可以执行以下操作零次或多次来获得分数：

  1. 选择一个未标记的敌人 i，使得 currentEnergy >= enemyEnergies[i]。选择此选项时：

    • 你获得 1 分
    • 你的能量减少敌人的能量，即 currentEnergy = currentEnergy - enemyEnergies[i]

  2. 如果你至少有 1 分，你可以选择一个未标记的敌人 i。选择此选项时：

    • 你的能量增加敌人的能量，即 currentEnergy = currentEnergy + enemyEnergies[i]
    • 敌人 i 被标记

通过最优地执行操作，返回你最终能获得的最大分数。

示例 1：

输入：enemyEnergies = [3,2,2], currentEnergy = 2
输出：3

示例 2：

输入：enemyEnergies = [2], currentEnergy = 10
输出：5

约束条件：

  • 1 <= enemyEnergies.length <= 10^5
  • 1 <= enemyEnergies[i] <= 10^9
  • 0 <= currentEnergy <= 10^9

解题思路

这道题的核心思路是贪心算法。

首先分析两种操作的本质：

  1. 第一种操作：消耗能量换取分数
  2. 第二种操作：标记敌人换取能量（需要至少1分）

关键观察：

  • 要获得分数，我们需要找到能量最小的敌人进行第一种操作
  • 一旦获得第一分，我们就可以通过第二种操作来"吸收"其他敌人的能量
  • 最优策略是先标记除了最小敌人外的所有敌人，获得它们的能量，然后用这些能量去击败最小的敌人获得更多分数

具体步骤：

  1. 找到能量最小的敌人
  2. 如果初始能量不足以击败最小敌人，返回0
  3. 先用最小敌人获得1分
  4. 标记其他所有敌人获得它们的能量
  5. 用所有能量去击败最小敌人获得最大分数

这样可以最大化利用能量，因为我们总是用最少的能量获得分数。

时间复杂度主要在于找最小值和求和，都是O(n)。

代码实现

class Solution {
public:
    long long maximumPoints(vector<int>& enemyEnergies, int currentEnergy) {
        int minEnergy = *min_element(enemyEnergies.begin(), enemyEnergies.end());
        
        // 如果初始能量不足以击败最小的敌人，无法获得任何分数
        if (currentEnergy < minEnergy) {
            return 0;
        }
        
        // 计算所有敌人的总能量
        long long totalEnergy = 0;
        for (int energy : enemyEnergies) {
            totalEnergy += energy;
        }
        
        // 用最小敌人获得第一分，然后标记其他所有敌人获得能量
        // 最终能量 = 初始能量 - 最小敌人能量 + 其他所有敌人能量
        // = 初始能量 + 总能量 - 2 * 最小敌人能量
        long long finalEnergy = currentEnergy + totalEnergy - minEnergy;
        
        // 用所有能量击败最小敌人获得分数
        return finalEnergy / minEnergy;
    }
};

class Solution:
    def maximumPoints(self, enemyEnergies: List[int], currentEnergy: int) -> int:
        min_energy = min(enemyEnergies)
        
        # 如果初始能量不足以击败最小的敌人，无法获得任何分数
        if currentEnergy < min_energy:
            return 0
        
        # 计算所有敌人的总能量
        total_energy = sum(enemyEnergies)
        
        # 用最小敌人获得第一分，然后标记其他所有敌人获得能量
        # 最终能量 = 初始能量 - 最小敌人能量 + 其他所有敌人能量
        # = 初始能量 + 总能量 - 2 * 最小敌人能量
        final_energy = currentEnergy + total_energy - min_energy
        
        # 用所有能量击败最小敌人获得分数
        return final_energy // min_energy

public class Solution {
    public long MaximumPoints(int[] enemyEnergies, int currentEnergy) {
        int minEnergy = enemyEnergies.Min();
        
        // 如果初始能量不足以击败最小的敌人，无法获得任何分数
        if (currentEnergy < minEnergy) {
            return 0;
        }
        
        // 计算所有敌人的总能量
        long totalEnergy = enemyEnergies.Sum(x => (long)x);
        
        // 用最小敌人获得第一分，然后标记其他所有敌人获得能量
        // 最终能量 = 初始能量 - 最小敌人能量 + 其他所有敌人能量
        // = 初始能量 + 总能量 - 2 * 最小敌人能量
        long finalEnergy = currentEnergy + totalEnergy - minEnergy;
        
        // 用所有能量击败最小敌人获得分数
        return finalEnergy / minEnergy;
    }
}

/**
 * @param {number[]} enemyEnergies
 * @param {number} currentEnergy
 * @return {number}
 */
var maximumPoints = function(enemyEnergies, currentEnergy) {
    const minEnergy = Math.min(...enemyEnergies);
    
    // 如果初始能量不足以击败最小的敌人，无法获得任何分数
    if (currentEnergy < minEnergy) {
        return 0;
    }
    
    // 计算所有敌人的总能量
    const totalEnergy = enemyEnergies.reduce((sum, energy) => sum + energy, 0);
    
    // 用最小敌人获得第一分，然后标记其他所有敌人获得能量
    // 最终能量 = 初始能量 - 最小敌人能量 + 其他所有敌人能量
    // = 初始能量 + 总能量 - 2 * 最小敌人能量
    const finalEnergy = currentEnergy + totalEnergy - minEnergy;
    
    // 用所有能量击败最小敌人获得分数
    return Math.floor(finalEnergy / minEnergy);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(1)

其中 n 是敌人数量。时间复杂度主要来自于遍历数组找最小值和计算总和，空间复杂度为常数级别。