day32 买卖股票的最佳时机Ⅱ 跳跃游戏 跳跃游戏Ⅱ
题目1：122 买卖股票的最佳时机Ⅱ
题目链接：122 买卖股票的最大时机Ⅱ
题意
整数数组prices[i]表示某股票的第i天的价格，每天可买卖股票且最多持有1股股票，返回最大利润
利润拆分，拆分为每天的利润 每天的正利润相加 得到总利润
局部最优：只收获每天的正利润 全局最优：利润最大
代码
class Solution {
public:int maxProfit(vector<int>& prices) {int result = 0;for(int i=1;i<prices.size();i++){if(prices[i]-prices[i-1]>0) result += prices[i]-prices[i-1];}return result;}
};- 时间复杂度：O(n)
- 空间复杂度：O(1)
题目2：55 跳跃游戏
题目链接：55 跳跃游戏
题意
非负整数数组数组中的每个元素代表在该位置可以跳跃的最大长度 是否能够到达最后一个下标
当前处于数组的第一个下标处
不看每次具体跳几步，只看覆盖范围是否包含终点 在覆盖范围内的位置都可以被跳到
局部最优：每次取最大的覆盖范围 全局最优：得到最大的覆盖范围
代码
class Solution {
public:bool canJump(vector<int>& nums) {int cover = 0;for(int i=0;i<=cover;i++){//更新覆盖范围cover = max(cover,i+nums[i]);if(cover>=nums.size()-1) return true;}return false;}
};- 时间复杂度: O(n)
- 空间复杂度: O(1)
题目3：45 跳跃游戏Ⅱ
题目链接：45 跳跃游戏Ⅱ
题意
非负整数数组元素nums[i]表示可以跳转的最大长度，返回到达最后一个元素的最小跳跃次数，初始位置为nums[0]
每一步尽可能地往远跳，一旦跳到终止位置，最少的跳跃步数增加覆盖范围
代码
class Solution {
public:int jump(vector<int>& nums) {int cur = 0;int next = 0;int result = 0;for(int i=0;i<nums.size();i++){next = max(next, i + nums[i]);if(i==cur){if(cur!=nums.size()-1){result++;cur = next;if(cur>=nums.size()-1) break;}}}return result;}
};- 时间复杂度: O(n)
- 空间复杂度: O(1)