LC-1696 Medium LeetCode

1696. Jump Game VI

Array Dynamic Programming Queue Heap (Priority Queue) Monotonic Queue

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 46% Topics: Array, Dynamic Programming, Queue, Heap (Priority Queue), Monotonic Queue

Reading material

Arrays & Hashing 12 min 1-D Dynamic Programming 16 min Stacks & Queues 11 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(k)

import collections


class Solution(object):
    def maxResult(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        score = 0
        dq = collections.deque()
        for i, num in enumerate(nums):
            if dq and dq[0][0] == i-k-1:
                dq.popleft()
            score = num if not dq else dq[0][1]+num
            while dq and dq[-1][1] <= score:
                dq.pop()
            dq.append((i, score))
        return score

Solution from kamyu104/LeetCode-Solutions · MIT