740. 删除并获得点数

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

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

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

示例 1：

1
2
3
4
5
输入：nums = [3,4,2]
输出：6
解释：
删除 4 获得 4 个点数，因此 3 也被删除。
之后，删除 2 获得 2 个点数。总共获得 6 个点数。

示例 2：

1
2
3
4
5
6
输入：nums = [2,2,3,3,3,4]
输出：9
解释：
删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。

提示：

  • 1 <= nums.length <= 2 * 104
  • 1 <= nums[i] <= 104

题解：

类似于“打家劫舍“升级版，提升了报警系统，在偷金额为3的房间的时候，金额为2和金额为4的房间会报警，但是其余金额为3的房间继续偷就不会触发报警系统。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public int deleteAndEarn(int[] nums) {
    /*
     * 每个位置上的数字都是在前两种结果的基础上进行选择的：
     *       1.如果不删除当前i位置元素，则得到的是前一个位置上元素的最优解。
     *       2.如果删除当前i位置元素，则会得到i -2 位置上的最优结果加上当前值乘以当前值的个数。
     *
     * 注：偷了第i位置上的元素之后，再偷这个元素就不会有问题。
     * 每次取以上两个结果中最大的值进行记录
     *
     *
     * 打家劫舍升级版
     * */
    int length = nums.length;

    if (nums == null || length == 0) {
        return 0;
    }

    if (length == 1) {
        return nums[0];
    }


    int max = nums[0];

    for (int i = 0; i < length; i++) {
        max = Math.max(max, nums[i]);
    }

    //构造一个记录数组元素出现次数的辅助数组
    //  nums:  2 , 4, 3, 2, 3, 3
    //  all:   0,  0, 2, 3, 1

    int[] all = new int[max + 1];
    for (int item : nums) {
        all[item]++;
    }
    
    //辅助dp数组
    int[] dp = new int[max + 1];
    //边界条件
    dp[1] = all[1] * 1;
    dp[2] = Math.max(dp[1], all[2] * 2);

    for (int i = 2; i <= max; i++) {
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + all[i] * i);
    }
    return dp[max];
}
  • 时间复杂度：O(N)，需要遍历数组。
  • 空间复杂度：O(N)，需要两个辅助数组。