Medium

题目描述

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

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

返回你能通过这些操作获得的最大点数。

示例 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）都会被强制删除。这意味着我们不能同时选择相邻的数字获得点数。

解题思路：

  1. 统计频次：用哈希表统计每个数字出现的次数，计算每个数字能获得的总点数
  2. 排序处理：将所有出现的数字排序，转化为在有序数组中选择不相邻元素的问题
  3. 动态规划：
    • dp[i] 表示考虑前 i 个不同数字时能获得的最大点数
    • 状态转移方程：
      • 如果当前数字与前一个数字相邻（差值为1），则 dp[i] = max(dp[i-1], dp[i-2] + 当前数字总点数)
      • 如果不相邻，则可以安全地加上当前数字：dp[i] = dp[i-1] + 当前数字总点数

这样就将原问题转化为了经典的动态规划问题，时间复杂度为 O(n log n)，主要消耗在排序上。

优化思路： 也可以直接用数组索引表示数字值（因为数字范围有限），避免排序，将复杂度优化到 O(n)。

代码实现

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        unordered_map<int, int> count;
        for (int num : nums) {
            count[num] += num;
        }
        
        vector<int> keys;
        for (auto& p : count) {
            keys.push_back(p.first);
        }
        sort(keys.begin(), keys.end());
        
        int prev2 = 0, prev1 = 0;
        for (int i = 0; i < keys.size(); i++) {
            int curr;
            if (i > 0 && keys[i] == keys[i-1] + 1) {
                curr = max(prev1, prev2 + count[keys[i]]);
            } else {
                curr = prev1 + count[keys[i]];
            }
            prev2 = prev1;
            prev1 = curr;
        }
        
        return prev1;
    }
};

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        from collections import defaultdict
        
        count = defaultdict(int)
        for num in nums:
            count[num] += num
        
        keys = sorted(count.keys())
        
        prev2 = prev1 = 0
        for i, key in enumerate(keys):
            if i > 0 and key == keys[i-1] + 1:
                curr = max(prev1, prev2 + count[key])
            else:
                curr = prev1 + count[key]
            prev2, prev1 = prev1, curr
        
        return prev1

public class Solution {
    public int DeleteAndEarn(int[] nums) {
        var count = new Dictionary<int, int>();
        foreach (int num in nums) {
            count[num] = count.GetValueOrDefault(num, 0) + num;
        }
        
        var keys = count.Keys.ToList();
        keys.Sort();
        
        int prev2 = 0, prev1 = 0;
        for (int i = 0; i < keys.Count; i++) {
            int curr;
            if (i > 0 && keys[i] == keys[i-1] + 1) {
                curr = Math.Max(prev1, prev2 + count[keys[i]]);
            } else {
                curr = prev1 + count[keys[i]];
            }
            prev2 = prev1;
            prev1 = curr;
        }
        
        return prev1;
    }
}

var deleteAndEarn = function(nums) {
    const count = new Map();
    for (const num of nums) {
        count.set(num, (count.get(num) || 0) + num);
    }
    
    const keys = Array.from(count.keys()).sort((a, b) => a - b);
    
    let prev2 = 0, prev1 = 0;
    for (let i = 0; i < keys.length; i++) {
        let curr;
        if (i > 0 && keys[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)统计频次O(n)，排序O(k log k)，DP遍历O(k)，其中k为不同数字个数
空间复杂度O(k)哈希表存储不同数字的点数，keys数组存储排序后的数字

相关题目