【LeetCode】第1696题——跳跃游戏VI（难度：中等）_给一个正整数列 nums,一个跳数 jump

题目描述

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

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

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

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

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

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

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

提示：
1 <= nums.length, k <= 10⁵
-10⁴ <= nums[i] <= 10⁴

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jump-game-vi
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

动态规划+单调队列

设定一个cost数组，其长度与nums一样，cost[i]代表跳跃至nums第 i 个元素所得到累加和的最大值。

如此一来就变成了cost[i] = max(cost[i-1], cost[i-2], …, cost[i-k]) + nums[i]。此等式是一个典型的动态规划，max()是一个典型的滑窗问题，使用单调队列进行解题。

代码详解