Leetcode 1696. Jump Game VI

題目

You are given a 0-indexed integer array nums and an integer k.

You are initially standing at index 0. In one move, you can jump at most k steps forward without going outside the boundaries of the array. That is, you can jump from index i to any index in the range [i + 1, min(n - 1, i + k)] inclusive.

You want to reach the last index of the array (index n - 1). Your score is the sum of all nums[j] for each index j you visited in the array.

Return the maximum score you can get.

想法

這題很容易想到一個 O(n*k) 的 DP 解法，但那樣會 TLE。

所以，我們要對 DP 更新的方式做一些改變。

我們多拿一個陣列當成 deque 來儲存位置需要處裡的位置。

這個 deque 有個特色，就是他是單調嚴格遞增的。

遍歷的時候，先把其中已經不在可抵達範圍內的拿掉。

該位置的 DP 值就會是 deque 最前面位置的最大分數加上該位置的分數。

你可能會想說，為什麼最前面位置的最大分數會最佳呢？

因為我們還會移除所有雖然在範圍內，但最大分數較該位置最大分數小的位置。

遍歷完就可以得到完整的 DP 陣列了，複雜度應該是 O(n)。

實作

Javascript

var maxResult = function (nums, k) {
  const n = nums.length;

  // dp 陣列用來存到 i 處最大分數
  let dp = new Array(n);
  // deque 用來存候選位置
  let deque = [];

  // 初始化，分別放入 i = 0 的值與位置
  dp[0] = nums[0];
  deque.push(0);

  // 遍歷 nums
  for (let i = 1; i < n; i++) {
    // 如果 deque 最前面那個超過可到達範圍，把它移除
    if (deque.length && deque[0] < i - k) deque.shift();

    // i 位置的最大分數會是 deque 中離 i 最遠的最大分數加上 i 位置的分數
    dp[i] = dp[deque[0]] + nums[i];

    // 把 deque 中位置的最大分數比 i 位置的最大分數小的位置移除
    while (deque.length && dp[i] >= dp[deque[deque.length - 1]]) deque.pop();

    // 把 i 位置放入 deque
    deque.push(i);
  }

  // 回傳到最後一個位置的最大分數
  return dp[n - 1];
};

• leetcode
• problem
• june challenge 2021