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

思路：贪心。把利润分解为每天为单位的维度,然后收集正利润的区间即可。

局部最优：收集每天的正利润，全局最优：求得最大利润。

// 贪心思路
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;}
}

2.55. 跳跃游戏

思路：贪心。将这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点！

局部最优解：每次取最大跳跃步数（取最大覆盖范围）。

整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

注意：只需要满足有一个位置能够直接指向最后的下标，且前面的位置可以到达这个位置。

public boolean canJump(int[] nums) {int count = 0;for (int i = 0; i <= count; i++) {// 每移动一个单位，就更新最大覆盖范围。// 注意i + nums[i]，必须得有一个位置直接指向最后的下标才能truecount = Math.max(count, i + nums[i]);// 当最大覆盖范围能指向最后一个下标时结束if (count >= nums.length - 1)return true;}return false;
}

3.45. 跳跃游戏 II

思路：贪心。

真正解题的时候，要从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最小步数！

这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。

• 其中只要下一步的最大覆盖能够覆盖到最后一个下标，则直接返回count+1；

• 若不能，则走到当前可覆盖的最大范围，count+1，并且更新下一步可覆盖的最大范围。

class Solution {public int jump(int[] nums) {if (nums == null || nums.length == 0 || nums.length == 1) {return 0;}//记录跳跃的次数int count = 0;//当前的覆盖最大区域int curjump = 0;//最大的覆盖区域int nextjump = 0;for (int i = 0; i < nums.length; i++) {//在可覆盖区域内更新最大的覆盖区域nextjump = Math.max(nums[i] + i, nextjump);//说明当前一步，再跳一步就到达了末尾if (nextjump >= nums.length - 1)return (count + 1);//走到当前覆盖的最大区域时，更新下一步可达的最大区域if (i == curjump){count++;curjump = nextjump;}}return count;}
}