1696. 跳跃游戏VI

题目描述：

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

一开始你在下标 0 处。每一步，你最多可以往前跳 k 步，但你不能跳出数组的边界。也就是说，你可以从下标 i 跳到 [i + 1， min(n - 1, i + k)] 包含 两个端点的任意位置。

你的目标是到达数组最后一个位置（下标为 n - 1 ），你的 得分 为经过的所有数字之和。

请你返回你能得到的 最大得分 。

示例 1：

输入：nums = [1,-1,-2,4,-7,3], k = 2
输出：7
解释：你可以选择子序列 [1,-1,4,3] （上面加粗的数字），和为 7 。 

示例 2：

输入：nums = [10,-5,-2,4,0,3], k = 3 
输出：17 
解释：你可以选择子序列 [10,4,3] （上面加粗数字），和为 17 。

示例 3：

输入：nums = [1,-5,-20,4,-1,3,-6,-3], k = 2 
输出：0

提示：

• 1 <= nums.length, k <= 10^5
• -10^4 <= nums[i] <= 10^4

---

解题分析及思路：

对应动态规划解法：

1. 状态定义： 定义 dp[i] 表示到达位置 i 时的最大得分。

2. 状态转移方程： 对于每个位置 i，我们可以从前面的某个位置 j 跳到 i，其中 j 的范围是 [i-k, i-1]。我们要找到使得 dp[j] 最大的 j，然后加上 nums[i] 就是 dp[i] 的值。即：

dp[i] = max(dp[j]...) + nums[i], 其中 j 的范围是 [i-k, i-1]

这个转移方程表示当前位置 i 的最大得分是前面某个位置 j 的最大得分加上当前位置的值。

3. 初始化： 初始时，dp[0] = nums[0]，表示初始位置的得分就是该位置的值。

4. 递推求解： 从左到右遍历数组，更新每个位置的最大得分。

5. 计算最终结果： 最终结果是 dp[n-1]，其中 n 是数组的长度。

其中：使用单调递减队列来维护 dp[j] 的最大值。队列中的元素按照 dp 的值从大到小排列，保证队列头部是最大的 dp[j]。每次需要找到当前位置 i 对应的 dp[j] 最大值时，就从队尾入队并不断出队，保持队列的单调递减性质。

func maxResult(nums []int, k int) int {
	l := len(nums)
	dp := make([]int, l)
	dp[0] = nums[0]
	// 单调递减队列
	queue := []int{0}
	for i := 1; i < l; i++ {
		// 1. 出队 (拿到队头，即最大值)
		if queue[0] < i-k {
			queue = queue[1:]
		}
		// 2. 转移
		dp[i] = dp[queue[0]] + nums[i]
		for len(queue) > 0 && dp[i] >= dp[queue[len(queue)-1]] {
			// 出队，直到队列元素大于dp[i]
			queue = queue[:len(queue)-1]
		}
		// 3. 入队
		queue = append(queue, i)
	}
	return dp[l-1]
}

复杂度：

• 时间复杂度：O(N)，其中 n 为输入数组 nums 的长度。
• 空间复杂度：O(N)，其中 n 为输入数组 nums 的长度。

执行结果：

• 执行耗时:91 ms,击败了94.87% 的Go用户
• 内存消耗:8.4 MB,击败了53.85% 的Go用户