740. 删除并获得点数
题目描述
输入整数数组 nums，初始得分为 0。
每次操作选出数组中的一个元素 x，把它移除并得到 x 分。随后数组中所有等于 x - 1 或 x + 1 的元素都要被移除，这些元素不计分。
可以进行任意多次操作。返回能得到的最高总分。
示例 1
输入：nums = [3,4,2] 输出：6
解释：取 4 得 4 分并清掉 3，再取 2 得 2 分，共 6 分。
示例 2
输入：nums = [2,2,3,3,3,4] 输出：9
解释：取 3 时清掉所有 2 和 4，再把三个 3 都取走，共 9 分。
数据范围
1 <= nums.length <= 2 * 10^41 <= nums[i] <= 10^4
解题思路：值域计数 + 打家劫舍
选了某个值 v，就应该把所有 v 都拿完，收益 total[v] = v × 出现次数；代价是 v-1 和 v+1 不能再选。于是问题变成在 total[1..m] 上“不能选相邻两个”的打家劫舍：用 take 表示选当前值的最优解，skip 表示不选当前值的最优解，每步 take = skip + total[v]，skip = max(take, skip)。
为什么正确
处理到值 v 后，take / skip 是只考虑 1..v 时“选了 v / 没选 v”的最大得分。
复杂度分析
时间 O(n + m)，空间 O(m)，m 是最大值。
易错点
不要在原数组的下标上做打家劫舍，“相邻”指的是值相差 1。更新 take 时必须用上一步的 skip，所以要同时赋值。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
m = max(nums)
total = [0] * (m + 1)
for x in nums:
total[x] += x
take, skip = 0, 0
for v in range(1, m + 1):
take, skip = skip + total[v], max(take, skip)
return max(take, skip)class Solution {
public int deleteAndEarn(int[] nums) {
int m = 0;
for (int x : nums) m = Math.max(m, x);
int[] total = new int[m + 1];
for (int x : nums)
total[x] += x;
int take = 0, skip = 0;
for (int v = 1; v <= m; v++) {
int nt = skip + total[v], ns = Math.max(take, skip);
take = nt; skip = ns;
}
return Math.max(take, skip);
}
}class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
int m = *max_element(nums.begin(), nums.end());
vector<int> total(m + 1, 0);
for (int x : nums)
total[x] += x;
int take = 0, skip = 0;
for (int v = 1; v <= m; v++) {
int nt = skip + total[v], ns = max(take, skip);
take = nt; skip = ns;
}
return max(take, skip);
}
};func deleteAndEarn(nums []int) int {
m := 0
for _, x := range nums {
m = max(m, x)
}
total := make([]int, m+1)
for _, x := range nums {
total[x] += x
}
take, skip := 0, 0
for v := 1; v <= m; v++ {
take, skip = skip+total[v], max(take, skip)
}
return max(take, skip)
}var deleteAndEarn = function(nums) {
const m = Math.max(...nums);
const total = new Array(m + 1).fill(0);
for (const x of nums)
total[x] += x;
let take = 0, skip = 0;
for (let v = 1; v <= m; v++) {
[take, skip] = [skip + total[v], Math.max(take, skip)];
}
return Math.max(take, skip);
};function deleteAndEarn(nums: number[]): number {
const m = Math.max(...nums);
const total = new Array(m + 1).fill(0);
for (const x of nums)
total[x] += x;
let take = 0, skip = 0;
for (let v = 1; v <= m; v++) {
[take, skip] = [skip + total[v], Math.max(take, skip)];
}
return Math.max(take, skip);
}其他解法
值域计数把问题直接变成打家劫舍，代码最短；排序分段只处理出现过的值，值域很大时更省时间和空间。
解法 2：排序 + 分段打家劫舍 时间 O(n log n)，空间 O(n)
先排序，把相同的数合并成（值，总和）对。依次处理每个不同的值：如果它等于上一个值加 1，两者不能同时选，按打家劫舍转移 take = skip + 总和、skip = max(take, skip)；否则两者互不影响，先把前面的最优值合并成 skip，再选当前值。
不依赖最大值 M，只和元素个数有关，适合数值很大但元素很少的情况。本题 M ≤ 10⁴，值域数组更简单。
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
nums = sorted(nums)
take = skip = 0
prev = None
i = 0
while i < len(nums):
v, s = nums[i], 0
while i < len(nums) and nums[i] == v:
s += v
i += 1
if prev is not None and v == prev + 1:
take, skip = skip + s, max(take, skip)
else:
skip = max(take, skip)
take = skip + s
prev = v
return max(take, skip)class Solution {
public int deleteAndEarn(int[] nums) {
Arrays.sort(nums);
int n = nums.length, take = 0, skip = 0, prev = -2, i = 0;
while (i < n) {
int v = nums[i], s = 0;
while (i < n && nums[i] == v) {
s += v;
i++;
}
if (v == prev + 1) {
int t = skip + s;
skip = Math.max(take, skip);
take = t;
} else {
skip = Math.max(take, skip);
take = skip + s;
}
prev = v;
}
return Math.max(take, skip);
}
}class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size(), take = 0, skip = 0, prev = -2, i = 0;
while (i < n) {
int v = nums[i], s = 0;
while (i < n && nums[i] == v) {
s += v;
i++;
}
if (v == prev + 1) {
int t = skip + s;
skip = max(take, skip);
take = t;
} else {
skip = max(take, skip);
take = skip + s;
}
prev = v;
}
return max(take, skip);
}
};func deleteAndEarn(nums []int) int {
sort.Ints(nums)
n, take, skip, prev, i := len(nums), 0, 0, -2, 0
for i < n {
v, s := nums[i], 0
for i < n && nums[i] == v {
s += v
i++
}
if v == prev+1 {
take, skip = skip+s, max(take, skip)
} else {
skip = max(take, skip)
take = skip + s
}
prev = v
}
return max(take, skip)
}var deleteAndEarn = function(nums) {
nums = [...nums].sort((a, b) => a - b);
const n = nums.length;
let take = 0, skip = 0, prev = -2, i = 0;
while (i < n) {
const v = nums[i];
let s = 0;
while (i < n && nums[i] === v) {
s += v;
i++;
}
if (v === prev + 1) {
[take, skip] = [skip + s, Math.max(take, skip)];
} else {
skip = Math.max(take, skip);
take = skip + s;
}
prev = v;
}
return Math.max(take, skip);
};function deleteAndEarn(nums: number[]): number {
nums = [...nums].sort((a, b) => a - b);
const n = nums.length;
let take = 0, skip = 0, prev = -2, i = 0;
while (i < n) {
const v = nums[i];
let s = 0;
while (i < n && nums[i] === v) {
s += v;
i++;
}
if (v === prev + 1) {
[take, skip] = [skip + s, Math.max(take, skip)];
} else {
skip = Math.max(take, skip);
take = skip + s;
}
prev = v;
}
return Math.max(take, skip);
}