题目

一个魔法师有许多不同的咒语。

给你一个数组 power ，其中每个元素表示一个咒语的伤害值，可能会有多个咒语有相同的伤害值。

已知魔法师使用伤害值为 power[i] 的咒语时，他们就不能使用伤害为 power[i] - 2 ，power[i] - 1 ，power[i] + 1 或者 power[i] + 2 的咒语。

每个咒语最多只能被使用一次。

请你返回这个魔法师可以达到的伤害值之和的 最大值 。

示例 1：

输入：power = [1,1,3,4]

输出：6

解释：

可以使用咒语 0，1，3，伤害值分别为 1，1，4，总伤害值为 6 。

示例 2：

输入：power = [7,1,6,6]

输出：13

解释：

可以使用咒语 1，2，3，伤害值分别为 1，6，6，总伤害值为 13 。

提示：

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

解题思路

这道题是一个典型的动态规划（Dynamic Programming, DP）问题，但它有一个关键的“陷阱”：咒语的伤害值 power[i] 可以高达 10^9。任何试图创建一个与伤害值范围一样大的数组的解法，都会因内存溢出而失败。

因此，正确的思路必须能够处理这种数据稀疏（sparse）且范围巨大的情况。

解题思路：稀疏动态规划 + 双指针优化

整个解法可以分为三个核心步骤：

第一步：数据预处理 (应对稀疏性)

问题的约束是基于伤害值，而不是咒语在原数组中的位置。并且，多个相同伤害值的咒语可以看作一个整体。因此，我们首先要整理和简化数据。

统计频率：使用一个哈希表 (map) 来统计每种独特伤害值的咒语出现了多少次。
- freq_map[伤害值] = 出现次数
- 例如，power = [3, 4, 4, 6] 会得到 freq_map = {3: 1, 4: 2, 6: 1}。
提取并排序：将哈希表中所有独特的伤害值（也就是 map 的键）提取到一个新的数组 unique_powers 中，并对这个数组进行升序排序。
- 对于上面的例子，unique_powers = [3, 4, 6]。

经过这一步，我们把问题从处理一个可能包含重复且无序的大数组，转化为了处理一个元素唯一且有序的小数组。DP 的规模将由 unique_powers 的大小决定，而不是 10^9。

第二步：定义动态规划状态 (核心)

我们的 DP 状态将基于 unique_powers 数组的索引，而不是伤害值本身。

dp[i] 的定义：只考虑前 i 种独特的伤害值 (即 unique_powers[0] 到 unique_powers[i-1]) 时，所能获得的最大伤害总和。

dp 数组的大小为 len(unique_powers) + 1。
我们的最终目标是求解 dp[len(unique_powers)]。

第三步：推导状态转移方程 (决策过程)

我们从 i = 1 开始，依次计算 dp 数组的每一项。在计算 dp[i] 时，我们关注的是第 i 种独特的伤害值，我们称之为 p = unique_powers[i-1]。

对于 p，我们面临两个选择：

不使用伤害值为 p 的咒语：
- 如果我们放弃使用所有伤害为 p 的咒语，那么能获得的最大伤害就和只考虑前 i-1 种咒语时一样。
- 此时，最大伤害为 dp[i-1]。
使用伤害值为 p 的咒语：
- 首先，我们会获得 p * freq_map[p] 的伤害值。
- 根据规则，使用了 p 就不能使用 p-1 和 p-2 的咒语。这意味着，我们能累加的之前部分的伤害，必须来自那些与 p 不冲突的咒语。
- 一个咒语 q 与 p 不冲突的条件是 q < p - 2。
- 我们需要找到一个历史最优解，这个解只使用了与 p 不冲突的咒语。由于 unique_powers 是有序的，我们只需要找到最后一个伤害值小于 p-2 的咒语，假设它的索引是 k (即 unique_powers[k] < p - 2)。那么，dp[k+1] 就代表了考虑 unique_powers[0...k] 之后得到的最大伤害，这正是我们需要的。
- 此时，总伤害为 (p * freq_map[p]) + dp[k+1]。

状态转移方程：dp[i] 的值就是这两个选择中的最大值。

第四步：优化查找过程 (双指针)

在上面的状态转移中，为每个 i 去从头查找那个临界索引 k 是很低效的（会导致 $O(n^2)$ 的复杂度）。

我们可以观察到：

当 i 增加时，p = unique_powers[i-1] 也是单调递增的。
因此，p-2 这个阈值也是单调递增的。
这意味着，我们为 i 寻找的那个兼容索引 k，也只会增加或保持不变，绝不会后退。

这个性质非常适合使用双指针技巧来优化。我们可以用一个慢指针 k 来追踪这个兼容边界。

算法流程总结

用哈希表 freq_map 统计 power 数组中每个数字的出现次数。
将 freq_map 的键提取到数组 unique_powers 中并排序。令 n 为其长度。
创建一个大小为 n+1 的 DP 数组 dp，并初始化为 0。
初始化一个慢指针 k = 0。
从 i = 1 遍历到 n： a. 获取当前伤害值 p = unique_powers[i-1]。 b. 移动慢指针：while k < i-1 并且 unique_powers[k] < p - 2，则 k++。 c. 计算不使用 p 的伤害：damage_option1 = dp[i-1]。 d. 计算使用 p 的伤害：damage_option2 = (p * freq_map[p]) + dp[k]。（注意：dp[k] 正好对应了 unique_powers[0...k-1] 的最优解）。 e. 更新 dp[i] = max(damage_option1, damage_option2)。
返回 dp[n]。

这个解法的时间复杂度主要由排序决定，为 $O(NlogN)$ 或者 $O(UlogU)$（其中 $N$ 是 power 数组长度，$U$ 是独特伤害值数量），空间复杂度为 $O(U)$。它既正确又高效，能够完美解决这道题。

具体代码

func maximumTotalDamage(power []int) int64 {
	// 1. 数据预处理
	// 当只有一个咒语时，直接返回其伤害值
	if len(power) == 1 {
		return int64(power[0])
	}

	// 使用哈希表统计每种伤害值的咒语【数量】
	sum_map := make(map[int]int)
	for _, num := range power {
		sum_map[num]++
	}

	// 提取所有独特的伤害值到一个切片中，用于后续排序和遍历
	sum_vector := make([]int, 0, len(sum_map))
	for key := range sum_map {
		sum_vector = append(sum_vector, key)
	}
	// 对独特的伤害值进行升序排序，这是动态规划的前提
	sort.Ints(sum_vector)

	// 2. 动态规划
	n := len(sum_vector)
	// dp[i] 表示考虑前 i 个独特伤害值 (sum_vector[0]...sum_vector[i-1]) 能获得的最大伤害
	dp := make([]int64, n+1)
	
	// k 是慢指针，用于高效查找与当前伤害值不冲突的最优子问题解
	k := 0 
	// 遍历所有独特的伤害值来填充dp数组
	for i := 1; i <= n; i++ {
		current_num := sum_vector[i-1]
		// 计算使用所有伤害值为 current_num 的咒语能造成的总伤害
		current_damage := int64(current_num) * int64(sum_map[current_num])

		// 移动慢指针 k，使其指向第一个与 current_num 【不兼容】的伤害值索引
		// 循环结束后，sum_vector[0...k-1] 中的所有伤害值都与 current_num 兼容
		for k < i-1 && sum_vector[k] < current_num-2 {
			k++
		}
		
		// 状态转移方程，在两种决策中取最大值：
		// 决策1 (dp[i-1]): 不使用当前伤害值(current_num)，则最大伤害等于考虑前 i-1 个独特伤害值的结果。
		// 决策2 (dp[k] + current_damage): 使用当前伤害值，则伤害为当前总伤害 + 与之兼容的历史最大伤害。
		// dp[k] 存储了 sum_vector[0...k-1] 范围内的最优解，正是我们需要的。
		dp[i] = max(dp[i-1], dp[k] + current_damage)
	}

	// dp[n] 存储了考虑所有独特伤害值后的最优解
	return dp[n]
}

3186. 施咒的最大总伤害

beautifulremi

题目