LeetCode 740. 删除并获得点数

约 5 分钟
文章信息 8 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 腾讯 字节 小红书
标签
数组 哈希表 动态规划

题目描述

✅ 740. 删除并获得点数

image-20260928224620806

image-20260928224620807

题意分析

每次选择并删除一个值 x，可以得到 x 点分数，同时必须删除数组中所有值为 x - 1 和 x + 1 的元素。被连带删除的元素不提供分数，求最终能得到的最大总分。

冲突由数值相差一决定，与元素在原数组中的下标是否相邻无关。同值元素不会互相删除，可以继续分别选择；输入顺序不影响最优结果。

解法：转化为打家劫舍

核心思路

[!blue]

一旦决定选择值 x，相邻数值的元素就不能再贡献分数，但其他等于 x 的元素仍然存在。把这些同值元素全部选完只会增加收益，不会产生新的冲突，所以可以预先合并：sum[x] 表示所有值为 x 的元素的分数总和，即数值乘以出现次数。

聚合后，只需在连续数轴上选择若干个值，不能同时选择相邻的两个数值，权重是 sum[x]，这就变成了打家劫舍。收益数组包含从零到最大值的所有位置，没有出现的值记为零收益；保留这些空档，才能正确表达距离大于一的值之间没有冲突。

处理当前数值 i 之前，take 表示考虑到 i - 1 且选择 i - 1 的最优收益，skip 表示考虑到 i - 1 且不选择它的最优收益。选择 i 必须跳过 i - 1，因此 takeNew = skip + sum[i]；不选择 i 就可以接受前一位置的任意状态，因此 skipNew = max(take, skip)。

两个新状态都必须从同一轮旧状态计算完，再一起覆盖。选或不选覆盖了当前值的全部合法选择，逐步保留两类最优结果，就能得到数轴前缀的整体最优解。最后最大数值也不一定值得选，答案应取最终 take、skip 的较大值。

解题步骤

  1. 找到数组中的最大值 M，建立长度为 M + 1 的收益数组。
  2. 对每个原元素 x，执行 sum[x] += x，聚合同值收益。
  3. 初始化 take = skip = 0，依次处理数值 0 到 M，包括零收益的空档。
  4. 先计算选择当前值和跳过当前值的两个新状态，再覆盖旧状态。
  5. 返回最终两种状态的最大值。

代码实现

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 为原数组长度，先聚合元素，再扫描完整数值范围。
  • 空间复杂度：$O(M + 1)$，用于收益表；动态规划只保存两个滚动状态。

关键点总结

[!green]

  • 同值元素可以全部获得收益，聚合后只需处理数值间的相邻冲突。
  • 数值空档必须保留为零收益位置，不能随意把所有出现值压成相邻位置。
  • 当前选择只能连接前一位置的不选状态，当前不选则接前一轮两类最优值。
  • 两个新值都算完再滚动，避免同一轮状态互相污染。

易错点总结

[!yellow]

  • 根据原数组下标判断冲突，误把位置相邻当成了数值相邻。
  • 聚合时只统计次数，没有乘上数值，改变了每次操作获得的分数。
  • 只按出现过的值顺次做打家劫舍，却不检查数值空档，会把不相差一的值误判为冲突。
  • 先覆盖 take 再计算 skip，会将本轮选择混入前一轮状态。
  • 最终只返回 take，相当于强制选择最大数值，可能错过更好的跳过方案。

相似题目

题目 难度 关联与区别
198. 打家劫舍 中等 先按数值聚合全部收益，再把相邻数值不能同时选择转成线性打家劫舍。
213. 打家劫舍 II 中等 比较选择当前元素与跳过当前元素的最优值；本题按值累计收益后禁止选择相邻值，该题拆开环形首尾冲突的两种情况。
337. 打家劫舍 III 中等 比较选择当前元素与跳过当前元素的最优值；本题按值累计收益后禁止选择相邻值，该题树上分别返回选根与不选根的结果。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/46642799
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！