java算法第32天 | 贪心算法 part02 ● 122.买卖股票的最佳时机II ● 55. 跳跃游戏 ● 45.跳跃游戏II

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

在这里插入图片描述

本题中理解利润拆分是关键点！不要整块的去看，而是把整体利润拆为每天的利润。假如第 0 天买入，第 3 天卖出，那么利润为：prices[3] - prices[0]。

相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。

一旦想到这里了，很自然就会想到贪心了，即：只收集每天的正利润，最后稳稳的就是最大利润了。

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

时间复杂度： $O (n)$
空间复杂度： $O (1)$

55. 跳跃游戏

在这里插入图片描述

本题的思路是不断更新覆盖范围，而不去纠结具体跳了几步。
局部最优：每次取最大的覆盖范围
全局最优：最终能覆盖的最大范围

class Solution {
    public boolean canJump(int[] nums) {
        int cover=0;
        if(nums.length==1) return true;
        for(int i=0;i<=cover;i++){
            cover=Math.max(i+nums[i],cover);
            if(cover>=nums.length-1) return true;//一旦到达终点了，直接return true；
        }
        return false;
    }
}

时间复杂度： $O (n)$
空间复杂度： $O (1)$

45.跳跃游戏II

在这里插入图片描述
本题的思路在于，每走一步都取能达到的最远位置。这就需要记录当前步的最远位置和下一步的最远位置，每当达到当前步的最远位置，直接走一步，并且把当前步的最远位置更新成下一步的最远位置，继续寻找下一步的最远位置，知道当前步的最远位置大于等于终点位置。

class Solution {
    public int jump(int[] nums) {
        if(nums.length==1) return 0;
        int nextMax=0;//记录下一步的最远位置
        int cur=0;//记录当前步的最远位置
        int step=0;//记录最终的结果
        for(int i=0;i<nums.length;i++){
            nextMax=Math.max(nextMax,i+nums[i]);
            if(i==cur){
                cur=nextMax;
                step++;//向前走一步
                if(cur>=nums.length-1) break;//如果走的这一步可以到达终点，直接break；
            }
        }
        return step;
    }
}