LeetCode 题解工作台
删除并获得点数
给你一个整数数组 nums ，你可以对它进行一些操作。 每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。 示例 1…
3
题型
4
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
class Solution: def deleteAndEarn(self, nums: List[int]) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个整数数组 nums ，你可以对它进行一些操作。
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
示例 1：
输入：nums = [3,4,2] 输出：6 解释： 你可以执行下列步骤： - 删除 4 获得 4 个点数，因此 3 也被删除。nums = [2]。 - 之后，删除 2 获得 2 个点数。nums = []。 总共获得 6 个点数。
示例 2：
输入：nums = [2,2,3,3,3,4] 输出：9 解释： 你可以执行下列步骤： - 删除 3 获得 3 个点数。所有的 2 和 4 也被删除。nums = [3,3]。 - 之后，再次删除 3 获得 3 个点数。nums = [3]。 - 再次删除 3 获得 3 个点数。nums = []。 总共获得 9 个点数。
提示：
1 <= nums.length <= 2 * 1041 <= nums[i] <= 104
解题思路
方法一
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
mx = -inf
for num in nums:
mx = max(mx, num)
total = [0] * (mx + 1)
for num in nums:
total[num] += num
first = total[0]
second = max(total[0], total[1])
for i in range(2, mx + 1):
cur = max(first + total[i], second)
first = second
second = cur
return second
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n + k log k) where n is the array length and k is the number of unique values due to map construction and sorting. Space complexity is O(k) for the map and DP arrays. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Checks if you recognize this is similar to the House Robber pattern using array scanning plus hash lookup.
- question_mark
Wants awareness of adjacency deletion impact and efficient aggregation per value.
- question_mark
Evaluates if you convert raw array input into a DP-ready format instead of naive recursive deletion.
常见陷阱
外企场景- error
Failing to combine all identical numbers before DP, leading to suboptimal picks.
- error
Ignoring that deleting a number affects adjacent numbers, causing off-by-one errors in totals.
- error
Attempting naive recursion or repeated scanning, resulting in TLE for large arrays.
进阶变体
外企场景- arrow_right_alt
Allow negative numbers, requiring offset mapping for hash array indexing.
- arrow_right_alt
Provide nums as a stream, requiring online aggregation before DP.
- arrow_right_alt
Modify to delete k-adjacent values instead of 1-adjacent, adjusting DP recurrence.