122.买卖股票的最佳时机II
122. 买卖股票的最佳时机 II - 力扣（LeetCode）
本题局部最优是只取相邻差值为正的情况，就可以得到全局最优利润最高，所以遍历整个数组，收集差值为正的即可
class Solution {
public int maxProfit(int[] prices) {
int result = 0;
for (int i = 1; i < prices.length; i++) {
result += Math.max(prices[i] - prices[i - 1], 0);
}
return result;
}
}
55. 跳跃游戏
本题不用纠结具体跳几步，而是考虑覆盖范围，看能否覆盖到最后一个元素
class Solution {
public boolean canJump(int[] nums) {
if (nums.length == 1) {
return true;
}
//覆盖范围就是可达到最大的数组下标
int cover = 0;
for (int i = 0; i <= cover; i++) {
cover = Math.max(cover, i + nums[i]);
if (cover >= nums.length - 1) {
return true;
}
}
return false;
}
}
45.跳跃游戏II
45. 跳跃游戏 II - 力扣（LeetCode）
本题仍然使用覆盖范围，只需要找出最早第几次覆盖可以达到末尾元素即可
class Solution {
public int jump(int[] nums) {
if (nums == null || nums.length == 0 || nums.length == 1) {
return 0;
}
int count = 0;
int curCover = 0; //当前覆盖范围
int nextCover = 0; //下个覆盖范围
for (int i = 0; i < nums.length; i++) {
//不断更新下个覆盖范围，取最大值
nextCover = Math.max(nextCover, i + nums[i]);
//下个覆盖范围到达了最后元素
if (nextCover >= nums.length - 1) {
count++;
break;
}
//走到当前覆盖范围的最后元素，并且没有达到数组最后元素，那么需要count++
if (i == curCover) {
count++;
curCover = nextCover; //更新curCover
}
}
return count;
}
}
