题目

给你一个整数数组 nums，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i]，删除它并获得 nums[i] 的点数。之后，你必须删除所有等于 nums[i] - 1 和 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

示例 1

输入：nums = [3,4,2]
输出：6
解释：删除 4 获得 4 点数，因此 3 也被删除；之后删除 2 获得 2 点数，总共 6。

示例 2

输入：nums = [2,2,3,3,3,4]
输出：9
解释：删除 3 获得 3 点数，接着要删除两个 2 和 4；之后再次删除 3 获得 3 点数，再删除 3 获得 3 点数，总共 9。

提示

  • 1 <= nums.length <= 2 * 10^4
  • 1 <= nums[i] <= 10^4

解题思路

这道题可以转化为打家劫舍问题：

  1. 首先统计每个数字出现的次数，记录在数组sum中
  2. sum[i]表示数字i出现的总和（即出现次数 × i）
  3. 选择某个数字i时：
    • 获得sum[i]的点数
    • 不能选择i-1和i+1
  4. 这就变成了：从一个数组中选数字，不能选相邻的数，求最大和

动态规划解法

  1. 定义dp[i]表示考虑前i个数字能获得的最大点数
  2. 对于数字i，可以选择要或不要：
    • 选择i：dp[i] = dp[i-2] + sum[i]
    • 不选i：dp[i] = dp[i-1]
  3. 取两种情况的最大值

Python 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        if not nums:
            return 0
            
        # 步骤1：构建数字和点数的映射
        points = {}
        for num in nums:
            points[num] = points.get(num, 0) + num
            
        # 获取所有不重复的数字并排序
        unique_nums = sorted(points.keys())
        n = len(unique_nums)
        
        # 特殊情况处理
        if n == 1:
            return points[unique_nums[0]]
            
        # 步骤2：初始化dp数组
        dp = [0] * n
        dp[0] = points[unique_nums[0]]
        
        # 如果第二个数和第一个数相差1，则不能同时选择
        if unique_nums[1] - unique_nums[0] == 1:
            dp[1] = max(dp[0], points[unique_nums[1]])
        else:
            # 如果不相邻，可以同时选择
            dp[1] = dp[0] + points[unique_nums[1]]
            
        # 步骤3：状态转移
        for i in range(2, n):
            curr_num = unique_nums[i]
            prev_num = unique_nums[i-1]
            
            if curr_num - prev_num == 1:
                # 如果相邻，则要考虑不选前一个数的情况
                dp[i] = max(dp[i-1], dp[i-2] + points[curr_num])
            else:
                # 如果不相邻，可以直接加上当前数的点数
                dp[i] = dp[i-1] + points[curr_num]
                
        return dp[-1]

Python解法说明

这个实现按照原来的思路，做了以下优化：

  1. 使用字典而不是数组来存储点数，节省空间
  2. 只考虑实际存在的数字，避免处理空隙
  3. 明确区分了相邻和不相邻数字的情况
  4. 特殊情况的处理更加完善

优点：

  • 实现更直观，符合题目的原始思路
  • 空间效率更高，只存储实际存在的数字
  • 时间复杂度保持O(n)，但实际运行更快

方法一：使用 Counter 简化统计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from collections import Counter

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        # 使用Counter直接统计每个数字的总和
        points = Counter(nums)  # 统计每个数字出现的次数
        nums = sorted(points.keys())  # 获取所有唯一的数字并排序
        
        # 初始化dp数组
        earn1, earn2 = 0, 0
        prev = -1  # 用于判断数字是否相邻
        
        # 遍历所有唯一的数字
        for num in nums:
            # 当前数字的总点数
            curr_earn = num * points[num]
            
            # 如果数字不相邻，可以直接加上之前的最大值
            if num - 1 != prev:
                earn2, earn1 = max(earn1, earn2) + curr_earn, earn2
            else:
                # 如果数字相邻，需要考虑是否选择当前数字
                earn2, earn1 = max(earn1, earn2 + curr_earn), earn2
            prev = num
            
        return max(earn1, earn2)

方法二：空间优化版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        if not nums:
            return 0
            
        # 只需要三个变量来维护状态
        prev = curr = future = 0
        count = [0] * (max(nums) + 1)
        
        # 统计每个数字的和
        for num in nums:
            count[num] += num
            
        # 动态规划，滚动更新
        for i in range(len(count)):
            future = max(curr, prev + count[i])
            prev, curr = curr, future
            
        return curr

Python解法说明

新的实现提供了两种优化方案：

  1. Counter版本的优点：

    • 使用内置的Counter类简化统计过程
    • 只遍历实际存在的数字，减少无效计算
    • 空间复杂度优化为O(k)，k为不同数字的个数

  2. 空间优化版本的优点：

    • 只使用三个变量维护状态，空间复杂度为O(1)
    • 代码更加简洁
    • 通过滚动数组思想优化空间使用

这两个版本都保持了相同的时间复杂度O(n)，但在空间使用和代码简洁性上有所改进。

复杂度分析

  • 时间复杂度：O(n)，其中n为nums数组中的最大值
  • 空间复杂度：O(n)，需要额外的数组来存储sum和dp值

总结

这是一道典型的动态规划问题，关键在于将原问题转化为类似打家劫舍的问题模型。通过合理定义状态转移方程，可以高效地解决这个问题。