1696：跳跃游戏 VI（1954 分）

Ian

2020-12-20 约 460 字预计阅读 1 分钟次阅读

力扣第 220 场周赛第 3 题

题目

给你一个下标从 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⁵
-10⁴ <= nums[i] <= 10⁴

分析

#1

类似 1425，令 dp[j] 代表到达位置 j 的最大得分，那么可以递推：

dp[j] = nums[j]+max(dp[j-k:j])

然后边递推边滑动 dp 数组，转为滑动窗口最大值问题。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


def maxResult(self, nums: List[int], k: int) -> int:
    from sortedcontainers import SortedList
    sl, dp = SortedList(), nums[:]
    for j, num in enumerate(nums):
        if j:
            dp[j] = num + sl[-1]
        sl.add(dp[j])
        if j>=k:
            sl.remove(dp[j-k])
    return dp[-1]

1376 ms

#2

也可以用单调队列的方法。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


def maxResult(self, nums: List[int], k: int) -> int:
    queue, dp = deque(), nums[:]
    for j, num in enumerate(nums):
        if j:
            dp[j] = num + queue[0][0]
        while queue and queue[-1][0]<=dp[j]:
            queue.pop()
        queue.append((dp[j], j))
        if queue[0][1] == j-k:
            queue.popleft()
    return dp[-1]

340 ms

目录

1696：跳跃游戏 VI（1954 分）

题目

分析

#1

#2

解答