LeetCode--3186. 施咒的最大总伤害

3186. 施咒的最大总伤害

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

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

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

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

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

---

同样是打家劫舍类型的题目，和之前的删除并获得点数的题很相似，但是此题的数据大小达到了 10^9 ，所以不能使用数组去 dp ，我们需要先用哈希表，然后将哈希表的 key 存入数组中，然后使用双指针移动索引，在基于数组和哈希表进行 dp 。

难点就在于这个思路，我们要知道，我们需要既需要去保证前一个状态的 key 和当前状态 key 相差等于 2 ，并且不能使用数组去记录每个 0 ~ key 的数量，此时就应该使用双指针，当差值大于 2 的时候，我们就可以移动双指针，直到差值为 2 ，此时就可以进行 dp 了，然而，我们如何去判断差值是否大于 2 ？此时将所有的 key（只包含 power 中给定的） 记录到数组中，然后遍历数组，同时维护一个指针记录数组的索引，当索引对应的元素和当前遍历的元素差值大于 2 ，则会移动指针，也就是移动到下一个元素，直到差值等于或者小于 2 ，就进行 dp 。

这里的关于 j 的计算有点难理解，其实就是选和不选的问题，不选，那么可以从 [0] ~ [i - 1] 的状态里面任意选择，如果要选，那么只能从 [0] ~ [j - 1] 里面选择，而 j 则是最小满足 nums[j] < x - 2 的元素下标，它刚好是不能选择的元素，所以它的前一个元素一定满足条件。

func maximumTotalDamage(power []int) int64 {
    mp := make(map[int]int, 0)
    for _, v := range power {
        mp[v] ++
    }
    n := len(mp)
    nums := make([]int, 0)
    for x := range mp {
        nums = append(nums, x)
    }
    slices.Sort(nums)
    f := make([]int, n + 1)
    j := 0
    for i, x := range nums {
        for nums[j] < x - 2 {
            j ++
        }
        f[i + 1] = max(f[i], f[j] + x * mp[x])
    }
    return int64(f[n])
}