740. 删除并获得点数

🟠 🔖 数组 哈希表 动态规划 🔗 力扣open in new window LeetCodeopen in new window

题目

You are given an integer array nums. You want to maximize the number of points you get by performing the following operation any number of times:

Pick any nums[i] and delete it to earn nums[i] points. Afterwards, you must delete every element equal to nums[i] - 1 and every element equal to nums[i] + 1.

Return themaximum number of points you can earn by applying the above operation some number of times.

Example 1:

Input: nums = [3,4,2]
Output: 6
Explanation: You can perform the following operations:
Delete 4 to earn 4 points. Consequently, 3 is also deleted. nums = [2].
Delete 2 to earn 2 points. nums = [].
You earn a total of 6 points.

Example 2:

Input: nums = [2,2,3,3,3,4]
Output: 9
Explanation: You can perform the following operations:
Delete a 3 to earn 3 points. All 2's and 4's are also deleted. nums = [3,3].
Delete a 3 again to earn 3 points. nums = [3].
Delete a 3 once more to earn 3 points. nums = [].
You earn a total of 9 points.

Constraints:

1 <= nums.length <= 2 * 10^4
1 <= nums[i] <= 10^4

题目大意

给你一个整数数组 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 * 10^4
1 <= nums[i] <= 10^4

解题思路

转换为打家劫舍问题：
- 由于删除 x 后需要同时删除 x-1 和 x+1，类似于 不能抢相邻房子的打家劫舍问题。
- 我们先统计 nums 中每个元素的 累加值：
  - count[x] = x * 出现次数
- 然后将 nums 去重并排序，得到一个新的 keys 数组。
状态定义：
- 设 dp[i] 表示 考虑到 keys[i] 时的最大得分。
- 转移方程：
  - 如果 keys[i] 和 keys[i-1] 连续（即 keys[i] = keys[i-1] + 1），有两种选择： dp[i] = max(dp[i-1], dp[i-2] + count[keys[i]])
  - 如果 keys[i] 和 keys[i-1] 不连续： dp[i] = dp[i-1] + count[keys[i]]
- 这与经典的 打家劫舍 (House Robber) 问题完全相同。
初始化：
- prev1 = 0（相当于 dp[i-2]）。
- prev2 = count[keys[0]]（相当于 dp[i-1]）。
计算最大得分：
- 采用滚动变量，遍历 keys 计算最大得分。

复杂度分析

时间复杂度：O(n log n)，因为需要对 keys 进行排序。
空间复杂度：O(n)，用于存储 count 映射。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var deleteAndEarn = function (nums) {
	let count = new Map();
	for (let num of nums) {
		count.set(num, (count.get(num) || 0) + num);
	}

	const keys = [...count.keys()].sort((a, b) => a - b);

	let prev1 = 0;
	let prev2 = count.get(keys[0]);

	for (let i = 1; i < keys.length; i++) {
		let temp;
		if (keys[i] == keys[i - 1] + 1) {
			temp = Math.max(prev2, prev1 + count.get(keys[i]));
		} else {
			temp = prev2 + count.get(keys[i]);
		}
		prev1 = prev2;
		prev2 = temp;
	}
	return prev2;
};

740. 删除并获得点数

# 740. 删除并获得点数

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

740. 删除并获得点数

题目

题目大意

解题思路

复杂度分析

代码

相关题目