1696. Jump Game VI

[TODO] Version #3 Segment Tree

二刷 07/2022

Version #2 Better DP + Sliding Window Maximum

比之前写的好了

一个是把space从O(N)优化到了O(k) - 因为只需要记录前k个index的dp value

另外一个就是stack里面只存index，然后通过index到dp的映射找到相对应的值

Time O(N)

Space O(k)

Runtime: 56 ms, faster than 51.27% of Java online submissions for Jump Game VI.

Memory Usage: 85.8 MB, less than 69.14% of Java online submissions for Jump Game VI.

class Solution {

    public int maxResult(int[] nums, int k) {

        // Use a monotonic decreasing deque in order to get the sliding window maximum

        int[] dp = new int[k];

        Deque<Integer> deque = new ArrayDeque<>();

        for (int i = 0; i < nums.length; i++) {

            // dp[i % k] - represents the max score to jump to index i

            int curr = nums[i];

            if (!deque.isEmpty()) {

                curr += dp[deque.peekFirst() % k];

            }

            // 0 1 2 - k = 2

            while (!deque.isEmpty() && dp[deque.peekLast() % k] < curr) {

                deque.pollLast();

            }

            deque.offerLast(i);

            dp[i % k] = curr;

            if (i - deque.peekFirst() == k) {

                deque.pollFirst();

            }

        }

        return dp[(nums.length - 1) % k];

    }

}

一刷 06/2022

Version #1 DP + Sliding Window Maximum

注意这道题和Sliding Window Maximum那道题的定义是有区别的，这道题的值是不包括当前点的前(i-k, i-1)个点的dp的max

看了答案，可以优化的地方是不需要同时存max和index，因为已经有了dp，只需要存index就可以通过index取到dp的值

Time O(N)

Space O(N)

Runtime: 70 ms, faster than 31.03% of Java online submissions for Jump Game VI.

Memory Usage: 108.7 MB, less than 39.20% of Java online submissions for Jump Game VI.

 class Solution {

    public int maxResult(int[] nums, int k) {

        int[] dp = new int[nums.length];

        dp[0] = nums[0];

        // int[0]-num, int[1]-index

        Deque<int[]> deque = new ArrayDeque<>();

        for (int i = 0; i < nums.length; i++) {

            // The max value between dp[i - k] and dp[i - 1]

            if (i == 0) {

                dp[i] = nums[0];

            } else {

                dp[i] = nums[i] + deque.peekFirst()[0];

            }

            

            if (i - k >= 0 && deque.peekFirst()[1] == i - k) {

                deque.pollFirst();

            }

            while (!deque.isEmpty() && dp[i] > deque.peekLast()[0]) {

                deque.pollLast();

            }

            deque.addLast(new int[]{dp[i], i});

            // System.out.printf("num=%d,max=%d\n", nums[i], deque.peekFirst()[0]);

            

        }

        return dp[nums.length - 1];

    }

}