友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
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 * 104 -
1 <= nums[i] <= 104
思路分析
最开始看错题目了，选择某个点数后，必须删除所有上下相邻的数字。
先统计每个点数的总和，然后就是 198. 打家劫舍 一样的解法了。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-04-18 15:23:34
*/
public int deleteAndEarn(int[] nums) {
int max = Arrays.stream(nums).max().getAsInt();
int[] sum = new int[max + 1];
for (int num : nums) {
sum[num] += num;
}
int a = sum[0];
// 只有头两个元素时，那个元素点数多。
// TODO 这里有个疑问：加入有 3✖1，,2✖2，
// 3✖1<2✖2，取完2后，还有一个 1，就不要了吗？
// 理解错了：选择某个点数后，必须删除“所有”相邻的数字
int b = Math.max(sum[0], sum[1]);
for (int i = 2; i < sum.length; i++) {
int tmp = b;
// dp[i] = max(array[i] + dp[i-2], dp[i-1])
b = Math.max(sum[i] + a, b);
a = tmp;
}
return b;
}