740. 删除并获得点数 - 力扣（LeetCode）
解法 1：动态规划（O(n) 时间，O(n) 空间）
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
if not nums:
return 0
# 统计每个数的贡献
points = Counter(nums)
max_val = max(nums) # 找到数组中的最大值
dp = [0] * (max_val + 1)
# 构造 dp 数组
for num in range(max_val + 1):
dp[num] = num * points[num]
# 打家劫舍
prev, curr = 0, 0
for num in range(max_val + 1):
prev, curr = curr, max(curr, prev + dp[num])
return curr✅ 时间复杂度：O(n)（遍历 nums 统计次数 + 遍历 dp 计算）
✅ 空间复杂度：O(n)（使用 dp 数组）
解法 2：优化的动态规划（O(n) 时间，O(1) 空间）
- 空间优化：只存储
prev和curr，减少dp数组占用。
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
if not nums:
return 0
points = Counter(nums)
max_val = max(nums)
prev, curr = 0, 0 # 滚动变量代替 dp 数组
for num in range(max_val + 1):
prev, curr = curr, max(curr, prev + num * points[num])
return curr✅ 时间复杂度：O(n)
✅ 空间复杂度：O(1)（只用两个变量）
总结
| 方法 | 时间复杂度 | 空间复杂度 | 适用情况 |
|---|---|---|---|
| DP 数组版 | O(n) | O(n) | 适用于小规模输入 |
| DP 滚动变量 | O(n) | O(1) | 推荐，适合大规模输入 |
最佳选择：用 滚动变量 版本，避免 O(n) 额外空间，适合大数据处理！ 🚀
