网站制作需要哪些软件,wordpress首页发布图片,网站建设好后有些什么资料,建筑工程资质查询平台文章目录1. 题目2. 解题2.1 贪心错误解2.2 优先队列/单调队列1. 题目
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
一开始你在下标 0 处。每一步#xff0c;你最多可以往前跳 k 步#xff0c;但你不能跳出数组的边界。 也就是说#xff0c;你可以从下标 i 跳到…
文章目录1. 题目2. 解题2.1 贪心错误解2.2 优先队列/单调队列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. 跳跃游戏 IVBFS LeetCode 1340. 跳跃游戏 VDP LeetCode LCP 09. 最小跳跃次数
2.1 贪心错误解
k 步以内遇到正的跳过去没有遇到正的跳到最大的负数上LC测试例子弱 [-1,-1,-4,-5,-4,-4,-4] k2这个例子不能通过下面程序输出 -14正解 -13
class Solution {
public:int maxResult(vectorint 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)O(nlogn)O(nlogn)
class Solution {
public:int maxResult(vectorint nums, int k) {int n nums.size(), ans nums[0];priority_queuepairint,int q;// sum. idxq.push({nums[0], 0});for(int i 1; i n; i) {while(i-q.top().second k)//这些位置不能跳到 i 位置q.pop();//能调过来的位置选最大的跳到 ians 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(vectorint nums, int k) {int n nums.size(), ans nums[0];dequepairint,int q;// sum. idxq.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博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
