Leetcode 1696 跳跃游戏 VI // 洛七的摸鱼池塘

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^5
-10^4 <= nums[i] <= 10^4

解答

本题的难度是 Medium.

昨天的是简单, 还以为今天的会是困难的. 这个题目很明显地可以用动态规划来解决, 因此我直接尝试一下, 就是看前面 [i-k, i-1] 到当前值的最大值, 为了避免第一次的时候 dp 的值可能是 0, 但是最大值是负数, 因此我直接初始化为 Integer.MIN_VALUE, 后面发现实际上这个根本不必要.

代码如下:

class Solution {
    public int maxResult(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MIN_VALUE);
        dp[0] = nums[0];
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= k; j++) {
                if(i-j>=0){
                    dp[i] = Math.max(dp[i], dp[i-j]+nums[i]);
                } else {
                    break;
                }
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[n-1];
    }
}

此时的时间复杂度为 O(n*k), 结果超时了, k=94270, 然后数组超级大的一个样例. 不仅会超时而且很抽象的是其实根本不需要这么一个初始化dp的过程, 因为其实本质就是看前面 k 个数的最大值是多少就行了, 后面加的值都是固定的, 那我们考虑降低时间复杂度, 看看能不能稳定地维护一个前 k 个值的最大值. 因此问题就转化为了求一个滑动窗口内的最大值. 我们通过单调队列去维护一个单调递减的队列, 这样就可以保证队头的元素是最大的, 然后我们每次都去维护这个队列, 使得队列的长度不超过 k, 这样就可以得到最大值了. 代码如下:

class Solution {
    public int maxResult(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MIN_VALUE);
        dp[0] = nums[0];
        Deque<Integer> deque = new ArrayDeque<>();
        deque.offer(0);
        for (int i = 1; i < n; i++) {
            // 先判断队头的元素是不是在滑动窗口范围内
            while(!deque.isEmpty() && deque.peek() <i-k){
                deque.poll();
            }
            // 现在都在队内了, 因此就可以判断了
            dp[i] = dp[deque.peek()]+nums[i];
            // 现在得到了新的值就去维护单调
            while(!deque.isEmpty() && dp[deque.peekLast()] < dp[i]){
                deque.pollLast();
            }
            deque.offer(i);
        }
        return dp[n-1];
    }
}

时间开销为 26ms, 击败了 47.47% 的提交, 只击败了不到一半的提交, 按照以往的经验是因为用了这种自带的类导致的, 我们可以看到, 其实我们的队列里面存的是下标, 而不是值, 因此我们可以用数组来模拟这个队列, 这样就可以减少一些时间开销. 代码如下:

class Solution {
    public int maxResult(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];
        // Arrays.fill(dp, Integer.MIN_VALUE);
        dp[0] = nums[0];
        int start = 0;
        int end = 0;
        int[] deque = new int[n+1];
        deque[start] = 0;
        for (int i = 1; i < n; i++) {
            // 先判断队头的元素是不是在范围内
            while(start <= end && deque[start] <i-k){
                start++;
            }
            // 现在都在队内了, 因此就可以判断了
            dp[i] = dp[deque[start]]+nums[i];
            // 现在得到了新的值就去维护单调
            while(start <= end && dp[deque[end]] < dp[i]){
                end--;
            }
            end++;
            deque[end] = i;
        }
        return dp[n-1];
    }
}

时间开销为 7ms, 击败了 93.04%, 暂时想不到什么方法可以更快了, 结果一看别人的方法, 维护一个最大值, 并记下他的下标, 当下标不在范围内的时候就重新遍历一遍前面的 k 个值, 找到最大值. (大概这个思路)

没想到这么简单粗暴的方式能够达到这样的时间效率.