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⁵

-10⁴ <= nums[i] <= 10⁴

解题思路#

单调递减队列。

from collections import deque
class Solution:
    def maxResult(self, nums: List[int], k: int) -> int:
        # 之前 k 步获得的最大值加上当前值
        desc_q = deque([])
        for i, x in enumerate(nums):
            while desc_q and desc_q[0][0] < i - k:
                desc_q.popleft()

            x += desc_q[0][1] if desc_q else 0
            while desc_q and desc_q[-1][1] <= x:
                desc_q.pop()

            desc_q.append([i, x])
        return desc_q[-1][1]

1696. 跳跃游戏 VI#

问题描述#

解题思路#

1696. 跳跃游戏 VI #