3186.施咒的最大总伤害：动态规划+双指针——O(1)空间（暂未发现其他O(1)空间的题解）

【LetMeFly】3186.施咒的最大总伤害：动态规划+双指针——O(1)空间（暂未发现其他O(1)空间的题解）

力扣题目链接：https://leetcode.cn/problems/maximum-total-damage-with-spell-casting/

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

给你一个数组 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 <= 105
• 1 <= power[i] <= 109

解题方法一：动态规划（O(n)空间）

首先二话不说对power数组来个哈希表统计和排序，得到这样的数组：[<1出现2次>, <3出现1次>, ...]。排序依据是power小的优先。

创建动态规划数组，dp[i+1]表示power[0]到power[i]所能达到的最大总伤害（dp[0]=0，此处power[i]代表排序后）。

这样就有状态转移方程：

$dp[i+1]=\max(dp[i], dp[j]+thisVal)$

其中$dp[i]$代表不使用当前power，$dp[j]$是最后一个满足$\lt power[i]-2$的power，$thisVal$代表使用这个power产生的总能量（$thisVal=power[i]\times times[i]$）。

现在就剩下最后一个问题了，如何快速得到小于$power[i]-2$的最大power是谁，也就是如何得到j的大小。

双指针即可。每当处理一个新$power[i]$时，当$power[j]\lt power[i]-2$时不断另$j+=1$即可。

• 时间复杂度$O(n\log n)$，其中$n=len(power)$，时间复杂度的来源主要是排序
• 空间复杂度$O(n)$，空间复杂度的来源主要是动态规划数组

AC代码

C++

/*
 * @LastEditTime: 2025-10-11 18:38:56
 */
typedef long long ll;
class Solution {
public:
    ll maximumTotalDamage(vector<int>& power) {
        unordered_map<int, int> cnt;
        for (int t : power) {
            cnt[t]++;
        }
        vector<pair<int, int>> values(cnt.begin(), cnt.end());
        sort(values.begin(), values.end());
        vector<ll> dp(values.size() + 1);
        for (int i = 0, j = 0; i < values.size(); i++) {
            auto& [value, times] = values[i];
            while (values[j].first < value - 2) {
                j++;
            }
            dp[i + 1] = max(dp[i], dp[j] + (ll) value * times);
        }
        return dp.back();
    }
};

Python

'''
Author: LetMeFly
Date: 2025-10-11 18:10:29
LastEditors: LetMeFly.xyz
LastEditTime: 2025-10-11 18:46:52
'''
from typing import List
from collections import Counter

class Solution:
    def maximumTotalDamage(self, power: List[int]) -> int:
        cnt = Counter(power)
        values = sorted(cnt)
        dp = [0] * (len(values) + 1)
        j = 0
        for i, val in enumerate(values):
            while values[j] < val - 2:
                j += 1
            dp[i + 1] = max(dp[i], dp[j] + val * cnt[val])
        return dp[-1]

解题方法二：动态规划（O(1)空间）

不难发现方法一中空间复杂度的来源主要是动态规划数组，并且不难发现动态规划数组只需要利用到最近几个。

这是因为和power[i]冲突的power范围向前看也就有个$power[i]-1$和$power[i]-2$，假设power中有这两个值，那么至多也就会用到两个前面的dp值。

所以可以使用数个变量来完成dp数组的原地滚动。

• 时间复杂度$O(n\log n)$，其中$n=len(power)$，时间复杂度的来源主要是排序
• 空间复杂度$O(1)$，相比于方法一，原地滚动大大简化了动态规划数组所需的空间

AC代码

Python

'''
Author: LetMeFly
Date: 2025-10-11 18:10:29
LastEditors: LetMeFly.xyz
LastEditTime: 2025-10-11 19:04:17
'''
from typing import List
from collections import Counter

class Solution:
    def maximumTotalDamage(self, power: List[int]) -> int:
        cnt = Counter(power)
        values = sorted(cnt)
        dp0 = dp1 = dp2 = 0
        val1 = val2 = -10
        for val in values:
            valSum = val * cnt[val]
            if val - val2 > 2:  # 无冲突
                useThis = valSum + dp2
            elif val - val1 > 2:  # 和val2相差小于2，但和val1不冲突
                useThis = valSum + dp1
            else:  # 和val1、val2都冲突(一定不会再和前面的冲突了)
                useThis = valSum + dp0
            dp = max(useThis, dp2)
            dp0, dp1, dp2 = dp1, dp2, dp
            val1, val2 = val2, val
        return dp2

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源