MediumRating 1954
1696. Jump Game VI
arraydynamic-programmingqueueheap-priority-queuemonotonic-queue
解題說明
Jump Game VI
題目描述:給定整數陣列 nums 和整數 k,從索引 0 出發,每步可跳 1 到 k 格。目標是到達最後一個索引,使經過位置的值之和最大。
解題思路:定義 dp[i] 為到達位置 i 的最大得分。轉移方程為 dp[i] = nums[i] + max(dp[i-k], ..., dp[i-1])。直接枚舉前 k 個位置需要 O(nk),用單調遞減佇列維護滑動窗口最大值可優化至 O(n)。佇列中保持 dp 值遞減,每次取隊首即為窗口最大值,並移除過期和較小的元素。
C++ 解法
複雜度分析
時間複雜度:O(n) — 每個元素最多進出單調佇列各一次。
空間複雜度:O(n) — DP 陣列和單調佇列各需 O(n) 空間。可優化佇列空間至 O(k)。
虛擬碼
1. Init dp[0] = nums[0] 2. Create monotonic deque, push index 0 3. For i = 1 to n-1: a. Remove front while front index < i - k (out of window) b. dp[i] = nums[i] + dp[deque.front] c. Remove back while dp[i] >= dp[deque.back] (maintain decreasing) d. Push i to deque 4. Return dp[n-1]
其他解法
最大堆 O(n log n):用最大堆維護 (dp[j], j) 配對。每次取堆頂的最大 dp 值,若索引過期則彈出。時間 O(n log n),不需要理解單調佇列。
線段樹 O(n log n):用線段樹支持區間最大值查詢。每次查詢 [i-k, i-1] 的最大值。實作較重但思路通用。
延伸思考
- 若每步跳躍本身有固定消耗 c,如何修改轉移方程?
- 若 k 不固定,而是每個位置有不同的最大跳躍距離 k[i]?
- 如何輸出達到最大得分的實際跳躍路徑?