【力扣一刷】代码随想录day32（贪心算法part2：122.买卖股票的最佳时机II、55. 跳跃游戏、45.跳跃游戏II ）

目录

【122.买卖股票的最佳时机II】中等题

方法一  贪心算法

方法二  动态规划

【55. 跳跃游戏】中等题

【尝试】 递归 （超时）

方法  贪心算法

【45.跳跃游戏II】中等题

方法  贪心算法

【122.买卖股票的最佳时机II】中等题（偏简单）

方法一  贪心算法

思路：

1、局部最优：截止到当天能赚到的最大利润

2、全局最优：截止到最后一天能赚到的最大利润就是全局最大利润

例子：上升就是赚钱机会，贪心地将每个赚钱机会把握住，获取赚到的钱的总和即可

class Solution {public int maxProfit(int[] prices) {int res = 0;for (int i = 0; i < prices.length - 1; i++){int delta = prices[i + 1] - prices[i];if (delta > 0) res += delta; // 贪心算法，不放过截止到现在的所有赚钱机会}return res;}
}

• 时间复杂度: O(n)，for循环遍历一次数组
• 空间复杂度: O(1)，没有额外的空间开销

方法二  动态规划

思路：

1、确定dp[i]的含义：截止到第i天赚到的最多的钱

2、确定递推关系：dp[i] = dp[i-1] + today

3、确定初始值：第一天赚到的最多的钱肯定是0，即dp[0] = 0

class Solution {public int maxProfit(int[] prices) {int dp = 0;for (int i = 1; i < prices.length; i++){// 今天之前赚到的最多的钱 + 今天当天赚到最多的钱 = 包括今天在内已经赚到的最多的钱int today = prices[i] - prices[i-1] > 0 ? prices[i] - prices[i-1] : 0;dp += today;}return dp;}
}

• 时间复杂度: O(n)，for循环遍历一次数组
• 空间复杂度: O(1)，dp[i]只与dp[i-1]有关，只用一个变量记录值即可

【55. 跳跃游戏】中等题

【尝试】 递归 （超时）

思路：

1、确定参数和返回值：传入数组和起跳索引作为参数，返回值为起跳索引能否到达最后一个索引的判断结果。

2、确定终止条件：当起跳索引为最后一个索引时，证明能够到达最后一个下标，返回true

3、确定单层递归逻辑：先获取当前起跳索引 start 能跳到的范围，一般是 [start + 1, start + nums[start]]。只需要遍历这个范围，如果这个范围内存在能否到达最后一个索引的索引即可返回true；for遍历结束后，在这个范围内的索引都无法到达最后一个索引，则该起跳索引无法到达最后一个索引，返回false。 

class Solution {public boolean canJump(int[] nums) {return canJumpToEnd(nums, 0);}public boolean canJumpToEnd(int[] nums, int start){// 起跳索引到达最后一个索引if (start == nums.length - 1) return true;// 计算起跳索引能到达的索引范围，如果索引范围超过数组的可索引范围，则取数组最大索引int longest = Math.min(start + nums[start], nums.length - 1);// for循环遍历每个start可到达的索引，如果有一个索引能到达最后一个索引就返回truefor (int i = start + 1; i <= longest; i++){if (canJumpToEnd(nums, i)) return true;}// for遍历完之后都到不了，则说明该索引无法到达最后一个索引，返回falsereturn false;}
}

方法  贪心算法

思路：

1、局部最优即获取遍历到的索引的最大覆盖范围，全局最优即遍历到最后相当于获取所有索引的最大覆盖范围，只要判断全局覆盖范围是否包含最后一个索引即可。

2、for循环遍历最大覆盖范围，每遍历一个索引就更新一次最大覆盖范围，判断最大覆盖范围是否包含了最后一个索引，是则返回true；

3、如果在最大覆盖范围内的索引都遍历完了也到达不了最后一个索引，则返回false

class Solution {public boolean canJump(int[] nums) {int longest = 0;for (int i = 0; i <= longest; i++){longest = Math.max(longest, i + nums[i]); // 更新最大覆盖范围if (longest >= nums.length - 1){  // 如果能到达最后一个索引，则返回true，还可以避免数组索引越界return true;}}return false; // 如果在最大覆盖范围内的索引都遍历完了也到达不了最后一个索引，则返回false}
}

• 时间复杂度: O(n)，for循环遍历一次数组
• 空间复杂度: O(1)

【45.跳跃游戏II】中等题（偏难）

方法  贪心算法

思路：

1、贪心策略：每跳一步，就贪心地获取这一步能到达的最远处，如果最远处超过最后一个索引，则一共所跳的次数就是最少的次数。

2、关键：如何获取每跳一步能到达的最远处？

例子：[2,3,1,2,4,2,3]      结果：3

• 第①次跳，只能从 i = 0 处开始跳，所以第①次跳能到达的最远处为 i = 2，最远处还没越过最后一个索引。
• 第②次跳，如果从 i = 1 处开始跳，能到达的最远处为 i = 4；如果从 i = 2 处开始跳，能到达的最远处为 i = 3；所以综合来看，第②次跳能到达的最远处为 i = 4，最远处还没越过最后一个索引。
• 第③次跳，如果从 i = 3 处开始跳，能到达的最远处为 i = 5；如果从 i = 4 处开始跳，能到达的最远处为 i = 8；所以综合来看，第③次跳能到达的最远处为 i = 8，已经越过了最后一个索引 i = 6。

3、步骤分析：

• 获取当前能到达的最远处。

• 判断当前能到达的最远处是否能到达最后一个索引，如果计算完下一跳的边界前（或到达当前跳的边界前）就已经能到达最后一个索引，则还需要再跳一次再返回结果。

• 如果上一跳能跳到的位置已经遍历完了（到达上一轮的边界时），则开启新一跳，次数+1，并设置新一跳的边界。

class Solution {public int jump(int[] nums) {int longest = 0;  // 用于记录已经遍历过的索引能到达的最远处int end = 0;  // 用于记录上一跳的边界/能到达的最远处int cnt = 0;  // 用于记录所跳的次数 for (int i = 0; i < nums.length - 1; i++){// 获取当前能到达的最远处longest = Math.max(longest, i + nums[i]);// 判断当前能到达的最远处是否能到达最后一个索引if (longest >= nums.length - 1){cnt++; // 如果计算完下一跳的边界前就已经能到达最后一个索引，则还需要再跳一次再返回结果break;}// 如果上一跳能跳到的位置已经遍历完了（到达上一轮的边界），则开启新一跳并设置新一跳的边界if (i == end){cnt++; // 开启新一跳，次数+1end = longest;  // 更新新一跳能到达的最远处/边界}}return cnt;}
}

• 时间复杂度: O(n)，for循环遍历一次数组
• 空间复杂度: O(1)