java算法第32天 | 贪心算法 part02 ● 122.买卖股票的最佳时机II ● 55. 跳跃游戏 ● 45.跳跃游戏II

本文主要是介绍java算法第32天 | 贪心算法 part02 ● 122.买卖股票的最佳时机II ● 55. 跳跃游戏 ● 45.跳跃游戏II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

122.买卖股票的最佳时机II

在这里插入图片描述

本题中理解利润拆分是关键点！不要整块的去看，而是把整体利润拆为每天的利润。假如第 0 天买入，第 3 天卖出，那么利润为：prices[3] - prices[0]。

相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。

一旦想到这里了，很自然就会想到贪心了，即：只收集每天的正利润，最后稳稳的就是最大利润了。

class Solution {public int maxProfit(int[] prices) {int result=0;for(int i=1;i<prices.length;i++){if(prices[i]-prices[i-1]>0){result+=(prices[i]-prices[i-1]);}}return result;}
}

时间复杂度： $O (n)$
空间复杂度： $O (1)$

55. 跳跃游戏

在这里插入图片描述

本题的思路是不断更新覆盖范围，而不去纠结具体跳了几步。
局部最优：每次取最大的覆盖范围
全局最优：最终能覆盖的最大范围

class Solution {public boolean canJump(int[] nums) {int cover=0;if(nums.length==1) return true;for(int i=0;i<=cover;i++){cover=Math.max(i+nums[i],cover);if(cover>=nums.length-1) return true;//一旦到达终点了，直接return true；}return false;}
}

时间复杂度： $O (n)$
空间复杂度： $O (1)$

45.跳跃游戏II

在这里插入图片描述
本题的思路在于，每走一步都取能达到的最远位置。这就需要记录当前步的最远位置和下一步的最远位置，每当达到当前步的最远位置，直接走一步，并且把当前步的最远位置更新成下一步的最远位置，继续寻找下一步的最远位置，知道当前步的最远位置大于等于终点位置。

class Solution {public int jump(int[] nums) {if(nums.length==1) return 0;int nextMax=0;//记录下一步的最远位置int cur=0;//记录当前步的最远位置int step=0;//记录最终的结果for(int i=0;i<nums.length;i++){nextMax=Math.max(nextMax,i+nums[i]);if(i==cur){cur=nextMax;step++;//向前走一步if(cur>=nums.length-1) break;//如果走的这一步可以到达终点，直接break；}}return step;}
}