122.买卖股票的最佳时机II
本题首先要清楚两点：
- 只有一只股票！
- 当前只有买股票或者卖股票的操作
想获得利润至少要两天为一个交易单元。
贪心算法
这道题目可能我们只会想，选一个低的买入，再选个高的卖，再选一个低的买入…循环反复。
如果想到其实最终利润是可以分解的，那么本题就很容易了！
如何分解呢？
假如第 0 天买入，第 3 天卖出，那么利润为：prices[3] - prices[0]。
相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。
此时就是把利润分解为每天为单位的维度，而不是从 0 天到第 3 天整体去考虑！
那么根据 prices 可以得到每天的利润序列：(prices[i] - prices[i - 1])…(prices[1] - prices[0])。
如图:
Java
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.跳跃游戏
思路
刚看到本题一开始可能想：当前位置元素如果是 3，我究竟是跳一步呢，还是两步呢，还是三步呢，究竟跳几步才是最优呢？
其实跳几步无所谓，关键在于可跳的覆盖范围！
不一定非要明确一次究竟跳几步，每次取最大的跳跃步数，这个就是可以跳跃的覆盖范围。
这个范围内，别管是怎么跳的，反正一定可以跳过来。
那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点！
每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。
贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。
Java
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;}
}
1. 为什么是 i <= coverRange？
i <= coverRange 的目的是限制迭代的范围，即只处理在当前「覆盖范围内」的位置。原因如下：
- 覆盖范围的定义：
coverRange是当前能到达的最远位置。 - 迭代条件的含义：当遍历到某个位置
i时，如果i已经超过了coverRange（即i > coverRange），说明从起点无法跳到位置i，因此也不可能再向后推进，直接返回false。
换句话说，i <= coverRange 确保我们只在能到达的位置范围内更新最远跳跃范围。
2.i + nums[i] 的意思是计算从当前位置 i 最远可以跳到的位置。
i是当前所在的位置索引。nums[i]是当前位置i上的数值，表示你在这个位置最多可以跳跃的步数。i + nums[i]就是从位置i最远可以到达的位置。
例子
假设 nums = [2, 3, 1, 1, 4]，逐步分析 i + nums[i] 的作用：
- 第 0 步 (
i = 0):- 当前
nums[0] = 2，所以从位置 0 最远可以跳到0 + 2 = 2。
- 当前
- 第 1 步 (
i = 1):- 当前
nums[1] = 3，所以从位置 1 最远可以跳到1 + 3 = 4。
- 当前
- 第 2 步 (
i = 2):- 当前
nums[2] = 1，所以从位置 2 最远可以跳到2 + 1 = 3。
- 当前
i + nums[i] 用于动态计算当前能到达的最大范围，以便更新 coverRange（当前覆盖范围）。
45.跳跃游戏II
思路
贪心的思路，局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最少步数。
要从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最少步数！
这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。
如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。
Java
class Solution {public int jump(int[] nums) {if(nums.length == 1 || nums.length == 0 || nums == null) return 0;int cur = 0; // 当前跳跃覆盖的最远位置int next = 0; // 下一次跳跃覆盖的最远位置int count = 0; // 跳跃次数for(int i = 0; i < nums.length; i++) {next = Math.max(next, i + nums[i]);if(i == cur) {if(cur != nums.length - 1) {count++;cur = next;if(cur >= nums.length - 1) break; // 如果已经可以到达终点，提前结束}else {count++;break;}}}return count;}
}
