贪心|122.买卖股票的最佳时机II、55.跳跃游戏、45.跳跃游戏II
122.买卖股票的最佳时机II
思路
局部最优：收集每天的正利润，全局最优：求得最大利润。
利润分解
代码：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int ans = 0;
for(int i = 0; i < prices.size() - 1; i++){
int price = prices[i + 1] - prices[i];
ans += max(price, 0);
}
return ans;
}
};
参考详解
55.跳跃游戏
思路
贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。
代码：
class Solution {
public:
bool canJump(vector<int>& nums) {
int cover = 0;
if(nums.size() == 1) return true;
for(int i = 0; i <= cover; i++){
cover = max(nums[i] + i, cover);
if (cover >= nums.size() - 1) {
return true;
}
}
return false;
}
};
参考详解
45.跳跃游戏II
思路
首先 起始位置为0，覆盖范围为零。然后遍历目前的数组，因为本题目一定有解，所以我们记录在目前的覆盖范围内最大的可跳跃值（在目前跳跃范围中我们最远可以到达的值）这个值是目前遍历的index加该index所对应的数组的值
（nums[i] + i）。当遍历到当前覆盖范围的末尾，我们首先发现覆盖范围小于数组长度，说明我们需要再跳跃一步，而且我们已经收集到了目前跳跃范围内，能跳跃到的最大位置。此时given我们需要再跳跃一步，我们要更新覆盖范围，这个新范围就是我们之前记录的最大范围值。
代码：
class Solution {
public:
int jump(vector<int>& nums) {
int cover = 0, cnt = 0, next = 0;
if(nums.size() == 1) return cnt;
for(int i = 0; i <= cover; i++) { //在覆盖范围内判断
next = max(next, nums[i] + i); //next 记录的是覆盖范围内的最大下一跳
if(i == cover) { //已经到达覆盖范围
if(cover < nums.size() - 1) { //但还未到达终点
cnt++; //跳数增加
cover = next; //跳到最大下一跳
if(cover >= nums.size() - 1) break; //到达终点结束
} else break;
}
}
return cnt;
}
};
