LeetCode 740. 删除并获得点数
目录
题目描述
题意分析
给定整数数组
nums，每次操作可以挑一个元素nums[i]删掉、获得等于nums[i]的点数，但代价是所有等于nums[i] - 1和nums[i] + 1的元素也必须一并删掉且拿不到分。可以操作任意多次，求最大总点数。读题的第一个关键点：连锁删除的对象是值而不是位置。删掉一个 5 之后，被清空的是所有的 4 和所有的 6，而其他的 5 一根汗毛都没少。这说明数组的下标顺序、元素的排列方式完全不影响答案——只有「每个值各出现多少次」才是有效信息。
第二个关键点由此推出：既然删一个 5 会连带清空 4 和 6，而剩下的 5 完好无损，那么理性的做法一定是把所有的 5 一次性全部吃掉。分几次吃不会额外损失什么（4 和 6 第一次就没了），却也不会多得。于是决策被压缩成对每个值的一次二元选择：这个值要么全取、要么不取。
第三个关键点：选了值
x之后，x-1和x+1就再也拿不到分了。把所有出现过的值按数轴排开，这条约束就是不能同时选相邻的两个整数。注意「相邻」指的是数值上差 1，而不是排序后位置上挨着——数组里若只有 2 和 7，它俩数值不相邻，可以同时选。数据规模上，数组长度不超过 $2 \times 10^4$，元素取值在 $[1, 10^4]$。值域上界很小且是正数，这条约束给得非常刻意：它允许我们开一个长度为 $10^4 + 1$ 的数组按数值直接索引，把「值」变成「下标」，从而让数轴上的相邻关系变成数组里的相邻下标。若值域无界或含负数，就得改用排序加分段处理。
边界有两处：某些数值在数组里根本没出现，它们的收益是 0，选不选都无所谓，但必须保留在数轴上占位，否则会把本来隔开的两个值误判成相邻；另外元素最小为 1，下标 0 恒为空档，不会造成越界。
解法：转化为打家劫舍
核心思路
先看暴力：把每个不同的值看作一个「选或不选」的开关，枚举所有子集，检查其中没有两个值相差 1，累加收益取最大。值最多有 $10^4$ 个，$2^{10^4}$ 个子集，完全不可行。
瓶颈在于枚举把「全局无相邻」这个约束当成了整体条件来事后检验。但这个约束其实是局部的：值
x能否被选，只取决于x-1有没有被选，和x-2及更小的值毫无关系。既然影响只跨一格，就可以按数值从小到大逐个决策，把已经定好的部分压缩成常数个状态。具体做法分两步。第一步是收益归并：扫一遍
nums，令sum[x]等于所有等于x的元素之和，也就是x * x 的出现次数。这一步把「同一个值出现多次」的重复信息压成一个数字，正是前面「同值必然全取」的观察的落地。归并之后，原问题变成：在数轴 $[0, maxVal]$ 上给每个整数标好权重sum[x]，选出一个不含相邻整数的集合使权重和最大。第二步就是这个新问题的线性 DP。它和打家劫舍完全同构——房子沿街排成一排，不能偷相邻两家，求最大金额；这里把「房子」换成「数值」、「金额」换成
sum[x]即可。注意这个同构关系成立的前提是数轴连续无跳跃，所以空缺的数值必须以权重 0 保留在序列里。状态定义取两个滚动量，含义要钉死：处理完数值
i之后，take表示「必须选了i」时的最大收益，skip表示「没有选i」时的最大收益。两者合起来覆盖了所有情况，因此任何时刻的最优解就是二者较大者。转移只有两条。要在
i处「选」，前一格就必须没选，所以take_i = skip_{i-1} + sum[i]。要在i处「不选」，前一格选没选都不受限，所以skip_i = max(skip_{i-1}, take_{i-1})。循环不变量是：每轮结束时，
take与skip分别等于「在前缀 $[0, i]$ 上、且i被选 / 未被选」这两类方案的最大收益。两条转移式各自只读上一轮的值，因此必须先把两个新值都算出来再一起赋值，不能算一个覆盖一个。最终答案取
max(take, skip)：最大的数值可选可不选，两种情形都要纳入比较。
解题步骤
- 先扫一遍
nums求出最大值maxVal。它决定了数轴的右端点，也决定了后面开的桶数组要多长。用实际最大值而不是固定的 $10^4$，可以让空间随输入自适应。- 开长度
maxVal + 1的数组sum，再扫一遍nums累加sum[num] += num。加的是数值本身而不是计数 1，因为要的是收益总额；累加而不是赋值，才能把重复出现的元素全部计入——这正是「同值全取」的体现。长度取maxVal + 1是为了让下标maxVal合法。- 初始化
take = 0、skip = 0。它们代表处理数值 0 之前的空前缀，此时无论选没选都还没有收益。由于题目保证元素至少为 1，sum[0]恒为 0，第一轮无论走哪个分支都不会引入伪收益。- 从
i = 0遍历到maxVal。必须逐个数值遍历而不是只遍历出现过的值，因为空缺的数值起着「隔离带」的作用：数组里只有 2 和 7 时，中间的 3 到 6 权重为 0，正是它们让 2 和 7 在递推中被判为互不冲突。跳过空缺会把它们错判成相邻。- 同时计算
takeNew = skip + sum[i]与skipNew = max(skip, take)，再一起赋回take、skip。两式读的都是上一轮的状态，若先执行take = skip + sum[i]再算skip = max(skip, take)，第二式里的take已经是本轮的新值，等于允许了「选了i又同时不选i」这种矛盾组合，结果会偏大。- 返回
max(take, skip)。只返回take会强制选中最大数值，只返回skip则强制不选，两者都可能错过最优。以
nums = [2, 2, 3, 3, 3, 4]走一遍。归并阶段：
maxVal = 4，sum = [0, 0, 4, 9, 4]（两个 2 合计 4，三个 3 合计 9，一个 4 合计 4）。初始
take = 0、skip = 0。
i = 0：sum[0] = 0，takeNew = 0 + 0 = 0，skipNew = max(0, 0) = 0，赋值后take = 0、skip = 0。
i = 1：sum[1] = 0，两值仍为take = 0、skip = 0。
i = 2：takeNew = skip + 4 = 4（选下全部的 2），skipNew = max(0, 0) = 0。赋值后take = 4、skip = 0。
i = 3：takeNew = skip + 9 = 0 + 9 = 9（选 3 就必须放弃 2，所以基数取的是「没选 2」的 0），skipNew = max(skip, take) = max(0, 4) = 4（不选 3 时，前面选 2 的方案 4 分更优）。赋值后take = 9、skip = 4。
i = 4：takeNew = skip + 4 = 4 + 4 = 8（选 4 就得放弃 3，基数取「没选 3」的 4，即选了 2 那一支），skipNew = max(4, 9) = 9。赋值后take = 8、skip = 9。返回
max(8, 9) = 9，对应方案是删掉三个 3，连带清空 2 和 4，得 9 分，确实优于「取 2 和 4 共 8 分」。若在
i = 3这一轮先更新了take再算skip，skipNew会读到刚写入的take = 9，得到skip = 9；到i = 4时takeNew = 9 + 4 = 13，最终返回 13——凭空同时吃下了 3 和 4，这正是覆盖旧值造成的典型错误。
代码实现
class Solution {
// 若选择 x，则不能选择 x-1 和 x+1，等价于打家劫舍问题。
public int deleteAndEarn(int[] nums) {
int maxVal = 0;
for (int num : nums) {
maxVal = Math.max(maxVal, num);
}
int[] sum = new int[maxVal + 1];
for (int num : nums) {
sum[num] += num;
}
int take = 0;
int skip = 0;
for (int i = 0; i <= maxVal; i++) {
int takeNew = skip + sum[i];
int skipNew = Math.max(skip, take);
take = takeNew;
skip = skipNew;
}
return Math.max(take, skip);
}
}
func deleteAndEarn(nums []int) int {
// 若选择 x，则不能选择 x-1 和 x+1，等价于打家劫舍问题。
maxVal := 0
for _, v := range nums {
if v > maxVal {
maxVal = v
}
}
sum := make([]int, maxVal+1)
for _, v := range nums {
sum[v] += v
}
take, skip := 0, 0
for i := 0; i <= maxVal; i++ {
takeNew := skip + sum[i]
skipNew := skip
if take > skipNew {
skipNew = take
}
take, skip = takeNew, skipNew
}
if take > skip {
return take
}
return skip
}
复杂度分析
- 时间复杂度：$O(n + M)$，其中 $n$ 是数组长度、$M$ 是数组中的最大值。凭的是两段独立的线性扫描：求最大值和累加收益各扫一遍
nums，是 $O(n)$；DP 沿数轴从 0 走到maxVal，每格只做两次算术和两次赋值，是 $O(M)$。两段不嵌套，所以相加而不是相乘。- 空间复杂度：$O(M)$。唯一的额外开销是长度为
maxVal + 1的收益桶数组；DP 部分只用了take、skip两个变量，因为转移只回看上一格，中间结果用完即弃。
关键点总结
- 当约束作用在值而不是位置上时，先做「按值归并」把问题从原数组搬到值域数轴上。这一步是本题的题眼，也是所有「操作某个数会连带影响相同数」类题目的通用第一招。
- 归并之后要问一句「新问题我见过吗」。这里「不能选相邻整数、求最大权重和」正是打家劫舍的裸形态，转化成功就等于把一道中等题降级成模板题——面试中把这条转化说清楚，比写对代码更能拿分。
- 值域小且为正是「开桶数组」的许可证。看到取值范围只有 $10^4$ 而元素个数有 $2 \times 10^4$，就该想到用值当下标；反过来若值域无界，就只能排序后按段处理，转化思路不变但实现要复杂得多。
- 空缺的数值必须以权重 0 保留在数轴上，它们是相邻性的隔离带。压缩序列（只保留出现过的值）会破坏相邻关系的判定，除非额外比较前后两值是否恰好差 1。
- 双状态 DP 的两条转移都读上一轮的值，务必先算后赋。凡是状态之间互相引用的递推，写代码时的默认姿势就是「算出所有新值，再统一赋值」，这条纪律能规避掉一大类静默错误。
- 面试视角：这题标准答法是先讲「同值必然全取」和「约束等价于不选相邻整数」两个观察，点明它就是 198 题，再写 $O(n + M)$ 的桶 DP，最后主动补一句「若值域很大而元素很少，改成排序去重后判断相邻值是否差 1，复杂度变成 $O(n \log n)$」。能给出值域相关的取舍，是这题区分度最高的地方。
易错点总结
- 先赋
take再算skip：写成take = skip + sum[i]; skip = Math.max(skip, take);，对nums = [2, 2, 3, 3, 3, 4]会返回 13（把 3 和 4 同时吃下），正确答案是 9。- 只遍历出现过的数值而不遍历整个数轴：对
nums = [2, 7]，若只把 2 和 7 排成序列做打家劫舍，会因为它们在序列里位置相邻而只取其中一个，返回 7；正确答案是 9，因为 2 和 7 数值上并不相邻。- 桶数组开成
new int[maxVal]：对nums = [3, 3]，maxVal = 3，累加sum[3]时立刻抛ArrayIndexOutOfBoundsException；长度必须是maxVal + 1。sum[num] += 1而不是+= num：对nums = [2, 2, 3]会把收益记成「个数」，算出max为 2（选两个 2 记 2 分）而不是 4，整个收益口径都错了。sum[num] = num覆盖而非累加：对nums = [2, 2, 3, 3, 3, 4]，sum变成[0, 0, 2, 3, 4]，返回max为 6 而不是 9，重复元素的收益全被丢掉。- 最后只返回
take：对nums = [2, 2, 3, 3, 3, 4]会返回 8（强制选中最大值 4），漏掉了不选 4 的更优解 9。- 最后只返回
skip：对nums = [3]会返回 0（强制不选最大值 3），正确答案是 3。- 误以为「删一个数就删掉全部同值元素」：按这个理解，
nums = [3, 3, 3]只能得 3 分；实际连锁删除的是x-1和x+1，同值元素安然无恙，答案是 9。- 贪心地按收益从大到小选：对
sum = [0, 0, 4, 5, 4]（即nums = [2, 2, 3, 3, 3, 4, 4]之类的构造）先选收益最高的 5，就再也拿不到两侧的 4 和 4，得 5 分；而放弃 5 改选两个 4 可得 8 分。相邻约束让局部最优不成立。- 用
HashMap存收益后按键的插入顺序做 DP：哈希表不保证有序，对nums = [1, 3, 2]可能按 1、3、2 的顺序递推，相邻关系彻底错乱，结果随实现而变。必须按数值升序遍历。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 198. 打家劫舍 | 中等 | 本题归并后的裸模板，不需要值域转化，直接在原数组上做双状态递推 |
| 213. 打家劫舍 II | 中等 | 序列首尾相接成环，需拆成「不取首」「不取尾」两条链各跑一次再取较大者 |
| 337. 打家劫舍 III | 中等 | 载体从数轴换成二叉树，双状态改为后序遍历时由左右子树的四个值合并 |
| 面试题 17.16. 按摩师 | 简单 | 与 198 同构的最简版本，适合先在这里把 take/skip 的更新顺序练熟 |
| LCR 089. 打家劫舍 | 中等 | 与 198 同题，可直接套用 |
| LCR 090. 打家劫舍 II | 中等 | 与 213 同题，可直接套用 |
| 1137. 第 N 个泰波那契数 | 简单 | 同为滚动变量递推，但状态间无互斥关系，可用来对照「先算后赋」纪律的必要性 |