LeetCode 1696. 跳跃游戏 VI（优先队列 / 单调队列）

Michael阿明

发布于 2021-02-19 15:01:22

48600

代码可运行

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

运行总次数：0

代码可运行

文章目录

1. 题目

给你一个下标从 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
-104 <= nums[i] <= 10^4

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/jump-game-vi 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

类似题目： LeetCode 45. 跳跃游戏 II（贪心/BFS，难） LeetCode 1306. 跳跃游戏 III（广度优先搜索BFS） LeetCode 1345. 跳跃游戏 IV（BFS） LeetCode 1340. 跳跃游戏 V（DP） LeetCode LCP 09. 最小跳跃次数

2.1 贪心错误解

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

class Solution {
public:
    int maxResult(vector<int>& 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 ( n l o g n ) O(nlogn) O(nlogn)

class Solution {
public:
    int maxResult(vector<int>& nums, int k) {
        int n = nums.size(), ans = nums[0];
        priority_queue<pair<int,int>> 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 ) O(n) O(n)

class Solution {
public:
    int maxResult(vector<int>& nums, int k) {
        int n = nums.size(), ans = nums[0];
        deque<pair<int,int>> 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++

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/12/20 ，如有侵权请联系 cloudcommunity@tencent.com 删除

游戏