Medium

题目描述

给你一个下标从 0 开始的整数数组 nums 和一个整数 k。

一开始你在下标 0 处。在一次移动中，你最多可以往前跳 k 步，但不能跳出数组的边界。也就是说，你可以从下标 i 跳到 [i + 1， min(n - 1, i + k)] 包含 两个端点的任意位置。

你的目标是到达数组最后一个位置（下标为 n - 1），你的 得分 为经过的所有 nums[j] 的和。

请你返回你能得到的 最大得分 。

示例 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

解题思路

这道题是一个经典的动态规划问题，可以用多种数据结构来优化。

基本思路： 定义 dp[i] 表示从位置 i 开始能获得的最大分数。状态转移方程为： dp[i] = nums[i] + max(dp[j]) 其中 j 在范围 [i+1, min(n-1, i+k)] 内。

暴力解法： 对每个位置 i，遍历所有可能的下一步位置计算最大值。时间复杂度 O(nk)。

优化解法：

  1. 单调队列优化：维护一个单调递减的双端队列，存储 (dp值, 索引) 对。队列头部始终是当前窗口内的最大值。
  2. 优先队列优化：使用最大堆维护窗口内的最大 dp 值，需要延迟删除过期元素。

推荐解法：单调队列，因为它的时间复杂度严格 O(n)，而优先队列在最坏情况下可能达到 O(n log n)。

算法步骤：

  1. 从右往左计算 dp 值
  2. 使用双端队列维护滑动窗口内的最大值
  3. 队列中元素按 dp 值单调递减排列
  4. 每次取队首元素作为当前位置的最优选择

代码实现

class Solution {
public:
    int maxResult(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> dp(n);
        deque<pair<int, int>> dq; // {dp值, 索引}
        
        dp[n-1] = nums[n-1];
        dq.push_back({dp[n-1], n-1});
        
        for (int i = n-2; i >= 0; i--) {
            // 移除超出范围的元素
            while (!dq.empty() && dq.front().second > i + k) {
                dq.pop_front();
            }
            
            // 计算当前位置的最大分数
            dp[i] = nums[i] + dq.front().first;
            
            // 维护单调递减队列
            while (!dq.empty() && dq.back().first <= dp[i]) {
                dq.pop_back();
            }
            dq.push_back({dp[i], i});
        }
        
        return dp[0];
    }
};

class Solution:
    def maxResult(self, nums: List[int], k: int) -> int:
        from collections import deque
        
        n = len(nums)
        dp = [0] * n
        dq = deque()  # (dp值, 索引)
        
        dp[n-1] = nums[n-1]
        dq.append((dp[n-1], n-1))
        
        for i in range(n-2, -1, -1):
            # 移除超出范围的元素
            while dq and dq[0][1] > i + k:
                dq.popleft()
            
            # 计算当前位置的最大分数
            dp[i] = nums[i] + dq[0][0]
            
            # 维护单调递减队列
            while dq and dq[-1][0] <= dp[i]:
                dq.pop()
            dq.append((dp[i], i))
        
        return dp[0]

public class Solution {
    public int MaxResult(int[] nums, int k) {
        int n = nums.Length;
        int[] dp = new int[n];
        var dq = new LinkedList<(int dp, int index)>();
        
        dp[n-1] = nums[n-1];
        dq.AddLast((dp[n-1], n-1));
        
        for (int i = n-2; i >= 0; i--) {
            // 移除超出范围的元素
            while (dq.Count > 0 && dq.First.Value.index > i + k) {
                dq.RemoveFirst();
            }
            
            // 计算当前位置的最大分数
            dp[i] = nums[i] + dq.First.Value.dp;
            
            // 维护单调递减队列
            while (dq.Count > 0 && dq.Last.Value.dp <= dp[i]) {
                dq.RemoveLast();
            }
            dq.AddLast((dp[i], i));
        }
        
        return dp[0];
    }
}

var maxResult = function(nums, k) {
    const n = nums.length;
    const dp = new Array(n);
    const dq = []; // [dp值, 索引]
    
    dp[n-1] = nums[n-1];
    dq.push([dp[n-1], n-1]);
    
    for (let i = n-2; i >= 0; i--) {
        // 移除超出范围的元素
        while (dq.length > 0 && dq[0][1] > i + k) {
            dq.shift();
        }
        
        // 计算当前位置的最大分数
        dp[i] = nums[i] + dq[0][0];
        
        // 维护单调递减队列
        while (dq.length > 0 && dq[dq.length-1][0] <= dp[i]) {
            dq.pop();
        }
        dq.push([dp[i], i]);
    }
    
    return dp[0];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型单调队列解法
时间复杂度O(n)
空间复杂度O(n)

说明：每个元素最多入队和出队一次，所以时间复杂度为 O(n)；空间复杂度主要由 dp 数组和双端队列占用。

相关题目