LeetCode 筆記 - 1696. Jump Game VI

Posted on 標籤
挑戰跳跳遊戲系列第六題，尋找路徑最高得分。雖然題目複雜度較高，本文分享利用最大堆積（Max Heap）優化搜尋過程的技巧：動態保存過去 k 個步驟中的最大分數，大幅提升動態規劃在長視窗下的執行效率。
⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。

題目在此 1696. Jump Game VI

給定一個分數數列與 k 值，每次你可以選擇 i + 1 ~ i + k 之間選擇你的下一個位置
請回傳最大分數

解題思維

這題是第四題，但其實跟前三題沒有大太關係
但如果你真的很想看看，那就讓你看看

第一題 LeetCode 筆記 - 55. Jump Game
第二題 LeetCode 筆記 - 45. Jump Game II
第三題 LeetCode 筆記 - 1306. Jump Game III

這題會很直覺的在第 i 的位置往前搜尋 k 尋找最大的數值
但其實還可以利用 Max Heap 儲存過去 k 個數字中最大的來加速

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def maxResult(self, nums: List[int], k: int) -> int:
        
        if (size := len(nums)) == 1:
            return nums[0]
        
        if k == 1:
            return sum(nums)
        
        score = nums[0]
        priority_queue = []
        
        # since heapq is a min-heap,
        # we use negative of the numbers to mimic a max-heap
        heapq.heappush(priority_queue, (-nums[0], 0))
        
        for i in range(1, size):

            # pop the old index
            while priority_queue[0][1] < i - k:
                heapq.heappop(priority_queue)
                
            score = nums[i] - priority_queue[0][0]
            heapq.heappush(priority_queue, (-score, i))
            
        return score

也許你也會想看看