本文共 2888 字，大约阅读时间需要 9 分钟。

1. 题目

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

一开始你在下标 0 处。每一步，你最多可以往前跳 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-104 <= nums[i] <= 10^4

来源：力扣（LeetCode） 链接：

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

类似题目：

2.1 贪心错误解

• k 步以内遇到正的，跳过去
• 没有遇到正的，跳到最大的负数上，LC测试例子弱 [-1,-1,-4,-5,-4,-4,-4] k=2，这个例子不能通过，下面程序输出 -14，正解 -13

class Solution {
   public:    int maxResult(vector
   
    & nums, int k) {
       	int n = nums.size(), ans = nums[0], maxNegative = INT_MIN, idx = -1;    	for(int i = 1; i < n; ++i)     	{
       		int step = k;    		bool inNegativePos = true;    		bool reachEnd = false;            maxNegative = INT_MIN;    		for( ; i < n && step--; i++)    		{
       			if(nums[i] >= 0)    			{
       				ans += nums[i];    				inNegativePos = false;    				break;    			}    			else    			{
       				if(i == n-1)    					reachEnd = true;    				if(nums[i] >= maxNegative)    				{
       					maxNegative = nums[i];    					idx = i;    				}    			}    		}    		if(inNegativePos)    		{
       			if(reachEnd)    			{
       				ans += nums[n-1];    				break;    			}    			else    			{
   	    			ans += nums[idx];	    			i = idx;	    		}    		}    	}    	return ans;    }};
   

2.2 优先队列/单调队列

• 优先队列，维护 i 之前的位置获得的最大和
• 跟当前的位置距离超过 K 的，pop掉，堆顶的位置跳到 i 是 i 处的最优值，存入堆中
• 时间复杂度 $O(nlogn)$

class Solution {
   public:    int maxResult(vector
   
    & nums, int k) {
           int n = nums.size(), ans = nums[0];        priority_queue
    
     
      > q;// sum. idx        q.push({
   nums[0], 0});        for(int i = 1; i < n; ++i)         {
               while(i-q.top().second > k)//这些位置，不能跳到 i 位置                q.pop();            //能调过来的位置，选最大的，跳到 i            ans = q.top().first + nums[i];// 到 i位置的最优选择            q.push({
   ans, i});//存入优先队列        }        return ans;    }};
     
    
   

848 ms 64.4 MB C++

• 单调队列，越靠后的点 j ，如果其位置的最大和不比前面 i 的小，那么 i 的值一定不是更优的选择，可以删掉，维护一个单调递减队列
• 时间复杂度 $O(n)$

class Solution {
   public:    int maxResult(vector
   
    & nums, int k) {
           int n = nums.size(), ans = nums[0];        deque
    
     
      > q;// sum. idx        q.push_back({
   nums[0], 0});        for(int i = 1; i < n; ++i)         {
               while(i-q.front().second > k)//这些位置，不能跳到 i 位置                q.pop_front();            ans = q.front().first + nums[i];// 到 i位置的最优选择            while(!q.empty() && q.back().first <= ans)                q.pop_back();            q.push_back({
   ans, i});//存入队列        }        return ans;    }};
     
    
   

308 ms 56.2 MB C++

我的CSDN

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

转载地址：https://michael.blog.csdn.net/article/details/111424091 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！