贪心算法章节理论基础：
https://programmercarl.com/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html
122.买卖股票的最佳时机II
题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
思路：
这道题目可能我们只会想，选一个低的买入，再选个高的卖，再选一个低的买入…循环反复。
如果想到其实最终利润是可以分解的，那么本题就很容易了！
假如第 0 天买入，第 3 天卖出，那么利润为：prices[3] - prices[0]。
相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。
此时就是把利润分解为每天为单位的维度，而不是从 0 天到第 3 天整体去考虑！
我们需要收集每天的正利润就可以，收集正利润的区间，就是股票买卖的区间，而我们只需要关注最终利润，不需要记录区间。
局部最优：收集每天的正利润，全局最优：求得最大利润。
class Solution {
public int maxProfit(int[] prices) {
int res = 0;
for(int i=1;i<prices.length;i++){
int tmp = prices[i]-prices[i-1];
if(tmp > 0)
res += tmp;
}
return res;
}
}
55. 跳跃游戏
题目链接：https://leetcode.cn/problems/jump-game/
思路：
这道题跳几步无所谓，关键在于可跳的覆盖范围。
不一定非要明确一次究竟跳几步，每次取最大的跳跃步数，这个就是可以跳跃的覆盖范围。
这个范围内，别管是怎么跳的，反正一定可以跳过来。
这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点。
每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。
贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。
class Solution {
public boolean canJump(int[] nums) {
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;
}
}
时间复杂度: O(n)
空间复杂度: O(1)
45.跳跃游戏II
题目链接：https://leetcode.cn/problems/jump-game-ii/description/
思路：
贪心的思路，局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最少步数。
所以真正解题的时候，要从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最少步数！
这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。
如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。
移动下标达到了当前覆盖的最远距离下标时，步数就要加一，来增加覆盖距离。最后的步数就是最少步数。
class Solution {
public int jump(int[] nums) {
if(nums.length <= 1) return 0;
int ans = 0;
int curDistance = 0; // 当前最远能去的地方
int nextDistance = 0; // 下一步最远能去的地方
for(int i=0;i<nums.length;i++){
nextDistance = Math.max(nums[i]+i,nextDistance);
if(i == curDistance){
ans ++;
curDistance = nextDistance;
if(nextDistance >= nums.length -1) break;
}
}
return ans;
}
}
小优化：
依然是贪心，思路和刚刚的方法差不多，代码可以简洁一些。
针对于方法一的特殊情况，可以统一处理，即：移动下标只要遇到当前覆盖最远距离的下标，直接步数加一，不考虑是不是终点的情况。
想要达到这样的效果，只要让移动下标，最大只能移动到 nums.size - 2 的地方就可以了。
-
如果移动下标等于当前覆盖最大距离下标， 需要再走一步（即 ans++），因为最后一步一定是可以到的终点。（题目假设总是可以到达数组的最后一个位置）
-
如果移动下标不等于当前覆盖最大距离下标，说明当前覆盖最远距离就可以直接达到终点了，不需要再走一步。
class Solution {
public int jump(int[] nums) {
if(nums.length <= 1) return 0;
int ans = 0;
int curDistance = 0; // 当前最远能去的地方
int nextDistance = 0; // 下一步最远能去的地方
// 优化版 如果是刚好等于倒数第二个格子，就说明还要再走一步。如果不等于，就说明最远的地方已经覆盖到了
for(int i=0;i<nums.length - 1;i++){
nextDistance = Math.max(nums[i]+i,nextDistance);
if(i == curDistance){
ans ++;
curDistance = nextDistance;
// if(nextDistance >= nums.length -1) break;
}
}
return ans;
}
}
时间复杂度: O(n)
空间复杂度: O(1)
