Google 面試實錄：RPG 連擊鏈 (O(N) 解法)

🎮 題目背景：RPG 裡的 Combo Chain

在一場 Google SDE 即時面試輔助中，我們遇到了一道看似輕鬆、實則暗藏殺機的題目——一個包裝成「RPG 遊戲連擊系統」的 Subsequence + DP 變種。

重點：

看起來像簡單的「最長遞增子序列 (LIS)」；
如果你條件反射寫 (O(N^2)) 的雙重迴圈，基本涼涼；
只有真正利用題目裡「固定差值為 1」這個關鍵資訊，才能寫出面試官心目中的 O(N) 最佳解。

在 oavoservice 的即時輔助下，這位客戶成功從 naive 思路躍遷到最佳解，並在 follow-up 中給出了空間友善的「路徑還原」方案，拿下 Google SDE Intern 的下一輪機會。

💬 題目要求（場景改編版）

Scenario: 你在玩一個 RPG 遊戲，每一關都有一個難度值，按陣列順序給出。 Goal: 你想打出一條最長的 "Combo Chain" 連擊。規則是：你選擇的每一關，下一關的難度必須剛好比上一關大 1。你可以跳過關卡，但必須保持原始順序。 Task: 返回這樣一條 Combo Chain 的 最大長度。

範例

Input:  [10, 5, 11, 6, 7, 12, 8]
Output: 4
Explanation: 最長合法鏈 5 -> 6 -> 7 -> 8
# 10 -> 11 -> 12 只有長度 3，更短

🧠 思路復盤：從 Clarification 到狀態定義

在面試開始的前 2 分鐘，oavoservice 先引導客戶完成關鍵 Clarification：

輸入為空返回 0。
是否必須連續下標？否，可以跳過（這是 subsequence，不是 subarray），但相對順序不能變。
難度是否必須 嚴格 +1？是的，這個約束非常關鍵。

很多候選人此時會直接套 最長遞增子序列 (LIS) 模板：

對於每個 nums[i]，回頭遍歷 0..i-1，找 nums[j] == nums[i] - 1。
dp[i] 表示以 i 結尾的最長長度。

複雜度：(O(N^2))。在 LeetCode 可能還能過，Google 面試基本宣判 思路不夠敏銳。

oavoservice 的關鍵提示：利用「固定差 1」壓縮到 O(N)

我們在協同螢幕上直接給出一個更高層的抽象：

「這是一個 difference 固定為 1 的子序列問題，可以用雜湊表記錄『以某個值結尾的最長鏈』。」

於是自然得到狀態定義：

dp[x] = 以難度 x 結尾的最長 Combo Chain 長度。

當遍歷到一個難度 x 時：

只需要看之前有沒有出現過 x - 1。
如果有，那麼當前值可以接在 dp[x - 1] 那條鏈後面：dp[x] = dp[x - 1] + 1。
如果沒有，x 自己就單獨開一條新鏈：dp[x] = 1。

全程只需一遍掃描 + 雜湊表，即可做到 O(N)。

💻 程式碼骨架（Python 版）

def longest_combo(levels):
    dp = {}          # dp[x] = 以難度 x 結尾的最長連擊長度
    max_combo = 0

    for level in levels:
        prev_length = dp.get(level - 1, 0)
        dp[level] = prev_length + 1
        max_combo = max(max_combo, dp[level])

    return max_combo

時間複雜度： (O(N))
空間複雜度： (O(N))

在 oavoservice 的提示下，客戶現場一次性寫對，沒有經歷 N^2 再優化的「繞路過程」，直接給出最佳解，面試官當場點頭認可。

🔁 Follow-up：如何返回具體的關卡序列

面試官緊接著拋出經典追問：

「如果我們不僅要返回長度，還要返回這串具體的關卡序列（例如 [5, 6, 7, 8]），怎麼辦？」

很多人第一反應是：

dp 中為每個值存一整條序列 List。
最終從中挑最長的那條。

這樣一來：

時間複雜度仍為 (O(N))，但
空間複雜度膨脹為 (O(N^2))，不夠優雅。

oavoservice 的極簡還原思路

我們給客戶的提示只有一句話：

「不要存 List，只要記住 最長鏈的結尾值 就行，剩下都能倒推。」

具體做法：

在更新 max_combo 時，同步記錄對應的 end_val。

if dp[level] > max_combo:
    max_combo = dp[level]
    end_val = level

已知：
- 最長長度 L = max_combo
- 結尾難度 end_val
那麼整條鏈一定是：
```
[end_val - L + 1, ..., end_val - 1, end_val]
```
倒推生成後即可得到從小到大的鏈條。

客戶在此基礎上，向面試官自然地解釋：

"Since the step is strictly +1, once I know the max length and the ending value, I can reconstruct the sequence in O(L) just by subtracting 1 repeatedly."

面試官評價："Simple and efficient."

🎓 面試啟示

看到「固定差值」的子序列問題，第一時間想 Hash Map，而不是雙重迴圈。
Follow-up 往往考察的是 空間和表達，不要條件反射地「把所有路徑都存下來」，多想想能不能根據結尾狀態反向推導。
面試不是背題，而是展示你如何從 naive solution 迭代到 optimal solution 的完整思考過程。

需要面試輔助服務？歡迎私信諮詢 oavoservice

📧 Email: [email protected]
📱 Phone: +86 17863968105

需要面試真題？立刻聯繫微信 Coding0201，獲得真題。