Medium

题目描述

一个魔法师有各种法术。

给你一个数组 power，其中每个元素代表一个法术的伤害值。多个法术可以有相同的伤害值。

众所周知，如果魔法师决定施放伤害为 power[i] 的法术，他们就不能施放伤害为 power[i] - 2、power[i] - 1、power[i] + 1 或 power[i] + 2 的任何法术。

每个法术只能施放一次。

返回魔法师可以施放的最大可能总伤害。

示例 1：

输入：power = [1,1,3,4]
输出：6
解释：
最大可能伤害 6 是通过施放伤害为 1、1、4 的法术 0、1、3 产生的。

示例 2：

输入：power = [7,1,6,6]
输出：13
解释：
最大可能伤害 13 是通过施放伤害为 1、6、6 的法术 1、2、3 产生的。

约束条件：

  • 1 <= power.length <= 10^5
  • 1 <= power[i] <= 10^9

提示：

  • 如果我们决定使用某个伤害值为 x 的法术，那么我们将使用所有伤害值为 x 的法术。
  • 考虑动态规划。
  • dp[i][j] 表示考虑前 i 个唯一法术且跳过 j 个法术时的最大伤害（根据约束最多跳过 3 个）。

解题思路

解题思路

这道题是一个典型的动态规划问题，核心约束是如果选择伤害值为 x 的法术，就不能选择伤害值为 x±1 或 x±2 的法术。

关键观察：

  1. 如果选择某个伤害值，就应该选择所有相同伤害值的法术（提示中明确说明）
  2. 问题转化为：选择一些不相邻的伤害值组，使得总伤害最大
  3. 相邻定义：伤害值差距在 1-2 之间

解法分析：

  1. 频次统计 + 排序：统计每个伤害值的出现次数，然后按伤害值排序
  2. 动态规划：对于每个唯一的伤害值，决定是否选择
    • dp[i] 表示考虑前 i 个唯一伤害值能获得的最大总伤害
    • 转移方程：选择当前伤害值时，需要跳过与它冲突的前面伤害值
  3. 优化查找：使用二分查找快速找到可以转移的最近位置

时间复杂度优化：

  • 朴素DP：O(n²)
  • 二分优化：O(n log n)

由于约束条件，对于当前伤害值 x，需要找到小于 x-2 的最大伤害值位置进行转移。

代码实现

class Solution {
public:
    long long maximumTotalDamage(vector<int>& power) {
        map<int, int> count;
        for (int p : power) {
            count[p]++;
        }
        
        vector<pair<int, long long>> spells;
        for (auto& [damage, cnt] : count) {
            spells.push_back({damage, (long long)damage * cnt});
        }
        
        int n = spells.size();
        vector<long long> dp(n + 1, 0);
        
        for (int i = 0; i < n; i++) {
            // 不选择当前法术
            dp[i + 1] = dp[i];
            
            // 选择当前法术，找到可以转移的位置
            int damage = spells[i].first;
            int left = 0, right = i;
            int pos = -1;
            
            while (left <= right) {
                int mid = (left + right) / 2;
                if (spells[mid].first < damage - 2) {
                    pos = mid;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            
            long long prev = (pos == -1) ? 0 : dp[pos + 1];
            dp[i + 1] = max(dp[i + 1], prev + spells[i].second);
        }
        
        return dp[n];
    }
};

class Solution:
    def maximumTotalDamage(self, power: List[int]) -> int:
        from collections import Counter
        import bisect
        
        count = Counter(power)
        spells = sorted([(damage, damage * cnt) for damage, cnt in count.items()])
        
        n = len(spells)
        dp = [0] * (n + 1)
        
        for i in range(n):
            # 不选择当前法术
            dp[i + 1] = dp[i]
            
            # 选择当前法术，找到可以转移的位置
            damage = spells[i][0]
            # 找到最大的伤害值 < damage - 2 的位置
            pos = bisect.bisect_left([s[0] for s in spells], damage - 2) - 1
            
            prev = 0 if pos < 0 else dp[pos + 1]
            dp[i + 1] = max(dp[i + 1], prev + spells[i][1])
        
        return dp[n]

public class Solution {
    public long MaximumTotalDamage(int[] power) {
        var count = new Dictionary<int, int>();
        foreach (int p in power) {
            count[p] = count.GetValueOrDefault(p, 0) + 1;
        }
        
        var spells = new List<(int damage, long total)>();
        foreach (var kvp in count) {
            spells.Add((kvp.Key, (long)kvp.Key * kvp.Value));
        }
        spells.Sort();
        
        int n = spells.Count;
        long[] dp = new long[n + 1];
        
        for (int i = 0; i < n; i++) {
            // 不选择当前法术
            dp[i + 1] = dp[i];
            
            // 选择当前法术，找到可以转移的位置
            int damage = spells[i].damage;
            int left = 0, right = i;
            int pos = -1;
            
            while (left <= right) {
                int mid = (left + right) / 2;
                if (spells[mid].damage < damage - 2) {
                    pos = mid;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            
            long prev = (pos == -1) ? 0 : dp[pos + 1];
            dp[i + 1] = Math.Max(dp[i + 1], prev + spells[i].total);
        }
        
        return dp[n];
    }
}

var maximumTotalDamage = function(power) {
    const freq = new Map();
    for (const p of power) {
        freq.set(p, (freq.get(p) || 0) + 1);
    }
    
    const unique = Array.from(freq.keys()).sort((a, b) => a - b);
    const n = unique.length;
    
    if (n === 0) return 0;
    if (n === 1) return unique[0] * freq.get(unique[0]);
    
    const dp = new Array(n);
    dp[0] = unique[0] * freq.get(unique[0]);
    
    if (unique[1] - unique[0] <= 2) {
        dp[1] = Math.max(dp[0], unique[1] * freq.get(unique[1]));
    } else {
        dp[1] = dp[0] + unique[1] * freq.get(unique[1]);
    }
    
    for (let i = 2; i < n; i++) {
        const curr = unique[i] * freq.get(unique[i]);
        
        if (unique[i] - unique[i-1] <= 2) {
            if (unique[i] - unique[i-2] <= 2) {
                dp[i] = Math.max(dp[i-1], dp[i-2] + curr);
            } else {
                dp[i] = Math.max(dp[i-1], dp[i-2] + curr);
            }
        } else {
            dp[i] = dp[i-1] + curr;
        }
    }
    
    return dp[n-1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n log n)
空间复杂度O(n)

其中 n 是不同伤害值的数量。时间复杂度主要来自排序和二分查找，空间复杂度用于存储计数、排序后的数组和DP数组。