_1696. Jump Game VI.md

1696. Jump Game VI

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 03, 2024

Last updated : July 03, 2024

---

Related Topics : Array, Dynamic Programming, Queue, Heap (Priority Queue), Monotonic Queue

Acceptance Rate : 45.77 %

---

Solutions

• m1696 v1 Heap.py
• m1696 v2 Deque.py
• m1696 v2 Deque.java

Python

m1696 v1 Heap.py

class Solution:
    def maxResult(self, nums: List[int], k: int) -> int:
        if len(nums) == 1 :
            return nums[0]
            
        hp = [(-nums[0], 0)]
        for i in range(1, len(nums) - 1) :
            while hp[0][1] < i - k :
                heapq.heappop(hp)
            heapq.heappush(hp, (-nums[i] + hp[0][0], i))

        while hp[0][1] < len(nums) - 1 - k :
            heapq.heappop(hp)

        return -hp[0][0] + nums[-1]

m1696 v2 Deque.py

class Solution:
    def maxResult(self, nums: List[int], k: int) -> int:
        if len(nums) == 1 :
            return nums[0]

        dp = deque()
        dp.append((nums[0], 0))

        for i in range(1, len(nums)) :
            while dp[-1][1] < i - k :
                dp.pop()
            val = dp[-1][0] + nums[i]

            while dp and (dp[0][0] <= val or dp[0][1] < i - k + 1) :
                dp.popleft()
            dp.appendleft((val, i))

        return dp[0][0]

Java

m1696 v2 Deque.java

class Solution {
    public int maxResult(int[] nums, int k) {
        ArrayDeque<Integer> vals = new ArrayDeque<Integer>();
        ArrayDeque<Integer> indices = new ArrayDeque<Integer>();

        vals.add(nums[0]);
        indices.add(0);

        for (int i = 1; i < nums.length; i++) {
            while (indices.getLast() < i - k) {
                indices.removeLast();
                vals.removeLast();
            }
            int val = vals.getLast() + nums[i];
            while (!indices.isEmpty() && (indices.getFirst() < i - k || vals.getFirst() < val)) {
                indices.removeFirst();
                vals.removeFirst();
            }
            indices.addFirst(i);
            vals.addFirst(val);
        }

        return vals.getFirst();
    }
}