代码随想录|贪心day2

122.力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

买股票的最佳时机，这道题其实和53有一点像，因为不需要写出哪个区间卖出买进，所以判断prices[i] - prices[i - 1]的值的大小，如果这个值是正的，那么就说明是可以抛出的就行，即收集每天的正利润得到全局最大利润。

class Solution {
    public int maxProfit(int[] prices) {
        int sum = 0;
        for(int i = 1;i<prices.length;i++){
            int num = prices[i] - prices[i - 1];
            if(num > 0){
                sum = sum + num;
            }
        }
        return sum;
    }
}

55.力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

这道题的关键在于 不要纠结每一步怎么走，而是看最大覆盖范围，覆盖范围内有交集则有解（首尾相连）。

i 在 cover 的范围内移动，每移动一个元素，cover 得到该元素数值（新的覆盖范围），如果cover能够 >= nums.length - 1,说明能到达。

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;
    }
}

45.力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

这个题的思想是要从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最少步数！
代码随想录讲的例子真的很好！看这个能看懂，画一个我自己理解的

class Solution {
    public int jump(int[] nums) {
        int result = 0;
        // 当前覆盖的最远距离下标
        int end = 0;
        // 下一步覆盖的最远距离下标
        int temp = 0;
        for (int i = 0; i <= end && end < nums.length - 1; ++i) {
            temp = Math.max(temp, i + nums[i]);
            // 可达位置的改变次数就是跳跃次数
            if (i == end) {
                end = temp;
                result++;
            }
        }
        return result;
    }
}