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]？
如何輸出達到最大得分的實際跳躍路徑？

Jump Game VI — CaffeCode