1696.跳跃游戏VI

链接：1696.跳跃游戏VI
难度：Medium
标签：队列、数组、动态规划、单调队列、堆（优先队列）
简介：你的目标是到达数组最后一个位置（下标为 n - 1 ），你的 得分 为经过的所有数字之和。请你返回你能得到的 最大得分 。

题解 1 - python

• 编辑时间：2024-02-05
• 执行用时：192ms
• 内存消耗：28.7MB
• 编程语言：python
• 解法介绍：单调队列。

class Solution:
    def maxResult(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp = [0] * n
        q = deque()
        for i in range(n):
            dp[i] += nums[i]
            while q and q[0] < i - k: q.popleft()
            if q: dp[i] += dp[q[0]]
            while q and dp[q[-1]] <= dp[i]: q.pop()
            q.append(i)
            # print(f'i = {i}, q = {q}, dp = {dp}')
        return dp[-1]