LeetCode 740: Delete and Earn ·

基本資料
#

難易度: medium 第一次嘗試：2026-04-25 來源：Day 11 learning note

學習脈絡
#

這篇是從 learning note 裡該 LeetCode 題目的段落重新整理出來的版本。我保留當天筆記中的修正點、比較點、容易犯錯的地方，並移除同一天其他非 LeetCode 主題，避免文章內容混題。

當天筆記摘錄
#

Problem 1 - LC 740 Delete and Earn
#

Status: Completed.
Pattern: Value bucketing -> House Robber.
Key insight: The conflict is between values x, x - 1, and x + 1, not between original array positions.

Why House Robber
#

If I take value x, I cannot take x - 1 or x + 1.

That is the same shape as:

take current bucket -> skip adjacent bucket
skip current bucket -> keep previous answer

So first convert:

points[x] = x * frequency(x)

Then solve House Robber on the points array.

State
#

dp[i] = maximum points we can earn using values from 0 to i

Base Case
#

dp[0] = 0
dp[1] = points[1]

Transition
#

dp[i] = max(dp[i - 1], dp[i - 2] + points[i])

Complexity
#

Time: O(n + m)
Space: O(m)

Where:

n = len(nums)
m = max(nums)

Interview-Ready Explanation
#

I group equal values first, because taking a value deletes only its neighboring values, not neighboring positions in the original array. I build points[x] as the total points from taking all xs. After that, the problem becomes House Robber on values: if I take x, I cannot take x - 1, so the transition is max(skip current, take current).

正確解法
#

上面的筆記保留了推理脈絡和當天需要修正的點。下面是我會提交的版本。

from typing import List

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        if not nums:
            return 0
        max_val = max(nums)
        points = [0] * (max_val + 1)
        for x in nums:
            points[x] += x

        prev2 = prev1 = 0
        for gain in points:
            prev2, prev1 = prev1, max(prev1, prev2 + gain)
        return prev1