LC 740. 删除并获得点数

题目描述

这是 LeetCode 上的 740. 删除并获得点数 ，难度为 中等。

给你一个整数数组 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 \times 10^4$
• $1 <= nums[i] <= 10^4$

---

动态规划

根据题意，当我们选择 $nums[i]$ 的时候，比 $nums[i]$ 大/小 一个单位的数都不能被选择。

如果我们将数组排好序，从前往后处理，其实只需要考虑“当前数”与“前一个数”的「大小 & 选择」关系即可，这样处理完，显然每个数的「前一位/后一位」都会被考虑到。

这样我们将问题转化为一个「序列 DP」问题（选择某个数，需要考虑前一个数的「大小/选择」状态）。

定义 $f[i][0]$ 代表数值为 $i$ 的数字「不选择」的最大价值；$f[i][1]$ 代表数值为 $i$ 的数字「选择」的最大价值。

为了方便，我们可以先对 $nums$ 中出现的所有数值进行计数，而且由于数据范围只有 $10^4$，我们可以直接使用数组 $cnts[]$ 进行计数：$cnts[x] = i$ 代表数值 $x$ 出现了 $i$ 次。

然后分别考虑一般性的 $f[i][0]$ 和 $f[i][1]$ 该如何计算：

• $f[i][0]$：当数值 $i$ 不被选择，那么前一个数「可选/可不选」，在两者中取 $max$ 即可。转移方程为 $f[i][0] = \max(f[i - 1][0], f[i - 1][1])$
• $f[i][1]$：当数值 $i$ 被选，那么前一个数只能「不选」，同时为了总和最大数值 $i$ 要选就全部选完。转移方程为 $f[i][1] = f[i - 1][0] + i * cnts[i]$

Java 代码：

class Solution {
    int[] cnts = new int[10009];
    public int deleteAndEarn(int[] nums) {
        int n = nums.length, max = 0;
        for (int x : nums) {
            cnts[x]++;
            max = Math.max(max, x);
        }
        // f[i][0] 代表「不选」数值 i；f[i][1] 代表「选择」数值 i
        int[][] f = new int[max + 1][2]; 
        for (int i = 1; i <= max; i++) {
            f[i][1] = f[i - 1][0] + i * cnts[i];
            f[i][0] = Math.max(f[i - 1][1], f[i - 1][0]);
        }
        return Math.max(f[max][0], f[max][1]);
    }
}

C++ 代码：

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int n = nums.size(), maxv = 0;
        vector<int> cnts(10009, 0);
        for (int x : nums) {
            cnts[x]++;
            maxv = max(maxv, x);
        }
        vector<vector<int>> f(maxv + 1, vector<int>(2, 0));
        for (int i = 1; i <= maxv; ++i) {
            f[i][1] = f[i - 1][0] + i * cnts[i];
            f[i][0] = max(f[i - 1][1], f[i - 1][0]);
        }
        return max(f[maxv][0], f[maxv][1]);
    }
};

Python 代码：

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        n, maxv = len(nums), 0
        cnts = [0] * 10009
        for x in nums:
            cnts[x] += 1
            maxv = max(maxv, x)
        f = [[0, 0] for _ in range(maxv + 1)]
        for i in range(1, maxv + 1):
            f[i][1] = f[i - 1][0] + i * cnts[i]
            f[i][0] = max(f[i - 1][1], f[i - 1][0])
        return max(f[maxv][0], f[maxv][1])

TypeScript 代码：

function deleteAndEarn(nums: number[]): number {
    let n = nums.length, maxv = 0;
    const cnts = new Array(10009).fill(0);
    for (const x of nums) {
        cnts[x] += 1;
        maxv = Math.max(maxv, x);
    }
    const f = Array.from({ length: maxv + 1 }, () => [0, 0]);
    for (let i = 1; i <= maxv; i++) {
        f[i][1] = f[i - 1][0] + i * cnts[i];
        f[i][0] = Math.max(f[i - 1][1], f[i - 1][0]);
    }
    return Math.max(f[maxv][0], f[maxv][1]);
};

• 时间复杂度：遍历 $nums$ 进行计数和取最大值 $max$，复杂度为 $O(n)$；共有 $max * 2$ 个状态需要被转移，每个状态转移的复杂度为 $O(1)$。整体复杂度为 $O(n + max)$。
• 空间复杂度：$O(n)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.740 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。