LeetCode刷题日记之贪心算法（二）

前言

在上一篇贪心算法的学习中，我们探讨了贪心算法的基本思路和逻辑框架。在这篇文章中，我将继续分享几道经典的LeetCode贪心算法题，并探讨其背后的解题思路和技巧。希望通过这些题目的实践，能加深我对贪心算法的理解，也为同样在刷题的小伙伴提供更多思考和启发✍✍✍

买卖股票的最佳时机II

LeetCode题目链接

这道题就是给一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格，然后每天你可以选择购入或者卖出，要求最大利润🤔🤔🤔

请添加图片描述

我们来思路梳理

我们使用贪心算法，通过局部最优来计算全局最优，如果今天的价格高于昨天的价格，我们就在昨天买入、今天卖出，赚取当天的差价🤔 通过不断选择局部最优解（每天都尽可能买卖股票赚取差价），累加所有的利润，最终获得最大利润🤔只要今天的价格比前一天高，就可以视为一个机会进行交易，赚取当天的利润。通过这样的贪心选择，可以确保我们获得最大利润🤔

很清晰的思路，我们直接来编码

class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0; //初始化最大利润为0

        //从第二天开始遍历数组
        for(int i = 1; i < prices.length; i++){
            //判断局部最优
            if(prices[i] > prices[i - 1]) maxProfit += prices[i] - prices[i - 1];//累加今天和昨天的差值作为利润
        }
        return maxProfit;
    }
}

代码也很简单，我们继续来学习下一道题✍✍✍

跳跃游戏

leetCode题目链接

这道题就是一个整数数组，数组每个数表示你在这个位置的最大可跳跃长度，初始在数组第一个下标，然后判断你能不能跳到数组最后一个下标处🤔🤔🤔

请添加图片描述

我们来思路梳理

这道题我们用贪心算法去解决的话，它的目标是判断能否从数组的第一个位置跳跃到最后一个位置，我们的核心思路就是在遍历数组的过程中 维护一个当前能到达的最远位置并逐步更新这个最远位置，判断它是否能够覆盖到最后一个下标🤔🤔🤔

这么说可能还是不够清晰，我们展开思路

每次在当前位置 i，根据当前元素 nums[i] 表示的最大跳跃长度，计算从当前位置能够跳到的最远位置。如果最远位置超过或等于数组的最后一个下标，说明可以到达。通过不断更新能够跳到的最远位置，确保我们总是选择最远的跳跃路径，以尽可能覆盖更多位置。如果最远位置最终覆盖到数组末尾，则可以到达最后一个下标🤔🤔🤔

这样已经很清楚了我们来进行编码

class Solution {
    public boolean canJump(int[] nums) {
        int maxReach = 0;//初始化最远可达位置

        for(int i = 0; i < nums.length; i++){//遍历数组元素
            //判断局部最优的可行性
            if(i > maxReach)return false;//已经超出最远可达位置了

            //更新问题状态
            maxReach = Math.max(maxReach, i + nums[i]);//更新最远可达位置

            if(maxReach >= nums.length - 1)return true;//可达最后位置
        }
        return true;
    }
}

这道题的核心就是一个最远可达位置变量的维护🤔🤔🤔

跳跃游戏II

LeetCode题目链接

这道题和上一道题相比就是这次不返回能否可达了，而是返回最小跳跃次数

请添加图片描述

我们来思路梳理

这道题和上道题不同的是这道题的关键在于如何选择每一步的跳跃，使得每次都能跳到最远的地方，从而减少跳跃次数🤔🤔🤔

我们来进一步梳理贪心的四个子逻辑

如何判断最优解
- 最优解是能够到达最后一个位置的最少跳跃次数 ，每一步都尽可能跳到最远的位置，以减少总跳跃次数。每次跳跃后更新跳跃范围，直到能跳到最后一个位置为止🤔🤔🤔
判断局部最优选择的可行性
- 局部最优选择是在当前能够跳跃的范围内，找到可以跳到的最远位置。当到达当前跳跃范围的边界时，我们就进行一次跳跃，并更新下一步的跳跃范围。这样可以确保我们每次都选择最远的跳跃，从而减少跳跃次数🤔🤔🤔
更新问题状态
- 每次跳跃时，我们更新两个状态，一个是下一步的跳跃范围（也就是最远跳跃位置），另一个是跳跃的次数（每次跳跃完成则跳跃次数加1）🤔🤔🤔
重复选择
- 遍历数组，逐步更新能够跳跃的最远位置，每次达到当前跳跃范围的边界时进行跳跃，直到能够跳到或超过最后一个位置🤔🤔🤔
我们在每一步的跳跃范围内，找到能够跳到的最远位置，一旦超出当前跳跃范围，就进行跳跃，并更新跳跃的范围。每次跳到最远位置时，跳跃次数加 1，直到能够到达或超过最后一个位置🤔🤔🤔

class Solution {
    public int jump(int[] nums) {
        int jump = 0;//初始化跳跃次数
        int maxReach = 0;//记录最远可达位置
        int endOfCurrentJump = 0;//记录当前跳跃范围的边界

        for(int i = 0; i < nums.length - 1; i++){//不需要遍历到最后一个数，能跳过去
            //判断局部最优选择的可信性
            maxReach = Math.max(maxReach, i + nums[i]);//更新最远可达位置

            //到达跳跃边界时进行跳跃
            if(i == endOfCurrentJump){
                jump++;
                endOfCurrentJump = maxReach;//更新下一次跳跃范围

                if(endOfCurrentJump >= nums.length - 1)break;
            }
        }
        return jump;
    }
}