【贪心算法】代码随想录算法训练营第三十二天 |122.买卖股票的最佳时机II，55.跳跃游戏，45.跳跃游戏II（待补充）

我不是女神ヾ 2024-04-23 04:17 56阅读 0赞

## 122.买卖股票的最佳时机II（未观看，动态待补充） ##

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ -]

2、文章讲解：[代码随想录][Link 1]

3、题目：

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

*  输入: \[7,1,5,3,6,4\]
 *  输出: 7
 *  解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:

*  输入: \[1,2,3,4,5\]
 *  输出: 4
 *  解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:

*  输入: \[7,6,4,3,1\]
 *  输出: 0
 *  解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

*  1 <= prices.length <= 3 \* 10 ^ 4
 *  0 <= prices\[i\] <= 10 ^ 4

4、视频讲解：

[贪心算法也能解决股票问题！LeetCode：122.买卖股票最佳时机II\_哔哩哔哩\_bilibili][LeetCode_122._II_bilibili]

5、思路：

本题首先要清楚两点：

*  只有一只股票！
 *  当前只有买股票或者卖股票的操作

想获得利润至少要两天为一个交易单元。

#### 贪心算法 ####

这道题目可能我们只会想，选一个低的买入，再选个高的卖，再选一个低的买入.....循环反复。

**如果想到其实最终利润是可以分解的，那么本题就很容易了！**

如何分解呢？

假如第 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\])。

如图：

![c7a7d1616213590df42be4b1c102d03d.png][]

一些同学陷入：第一天怎么就没有利润呢，第一天到底算不算的困惑中。

第一天当然没有利润，至少要第二天才会有利润，所以利润的序列比股票序列少一天！

从图中可以发现，其实我们需要收集每天的正利润就可以，**收****集正利润的区间，就是股票买卖的区间，而我们只需要关注最终利润，不需要记录区间**。

那么只收集正利润就是贪心所贪的地方！

**局部最优：收集每天的正利润，全局最优：求得最大利润**。

局部最优可以推出全局最优，找不出反例，试一试贪心！

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

class Solution {
        public int maxProfit(int[] prices) {
            int result = 0;
            for (int i = 1; i < prices.length; i++) {
                只累加利润为正的
                result += Math.max(0, prices[i] - prices[i - 1]);
            }
            return result;
        }
    }

## 55.跳跃游戏 ##

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ - 1]

2、文章讲解：[代码随想录][Link 2]

3、题目：

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

*  输入: \[2,3,1,1,4\]
 *  输出: true
 *  解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例 2:

*  输入: \[3,2,1,0,4\]
 *  输出: false
 *  解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

4、视频链接：

[贪心算法，怎么跳跃不重要，关键在覆盖范围 | LeetCode：55.跳跃游戏\_哔哩哔哩\_bilibili][_ LeetCode_55._bilibili]

5、思路：

刚看到本题一开始可能想：当前位置元素如果是 3，我究竟是跳一步呢，还是两步呢，还是三步呢，究竟跳几步才是最优呢？

其实跳几步无所谓，关键在于可跳的覆盖范围！

不一定非要明确一次究竟跳几步，每次取最大的跳跃步数，这个就是可以跳跃的覆盖范围。

这个范围内，别管是怎么跳的，反正一定可以跳过来。

**那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点！**

每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。

**贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点**。

局部最优推出全局最优，找不出反例，试试贪心！

如图：

![b9a5a5294dec933a15b6080df61cf3af.png][]

i 每次移动只能在 cover 的范围内移动，每移动一个元素，cover 得到该元素数值（新的覆盖范围）的补充，让 i 继续移动下去。

而 cover 每次只取 max(该元素数值补充后的范围, cover 本身范围)。

如果 cover 大于等于了终点下标，直接 return true 就可以了。

**总结：**

这道题目关键点在于：**不用拘泥于每次究竟跳几步，而是看覆盖范围，覆盖范围内一定是可以跳过来的，不用管是怎么跳的。**

大家可以看出思路想出来了，代码还是非常简单的。

一些同学可能感觉，我在讲贪心系列的时候，题目和题目之间貌似没有什么联系？

**是真的就是没什么联系，因为贪心无套路**！没有个整体的贪心框架解决一系列问题，只能是接触各种类型的题目锻炼自己的贪心思维！

class Solution {
        public boolean canJump(int[] nums) {
            if (nums.length == 1) {
                return true;
            }
            // 覆盖范围, 初始覆盖范围应该是0，因为下面的迭代是从下标0开始的
            int coverRange = 0;
            // 在覆盖范围内更新最大的覆盖范围
            for (int i = 0; i <= coverRange; i++) {
                coverRange = Math.max(i + nums[i], coverRange);
                if (coverRange >= nums.length - 1) {
                    return true;
                }
            }
            return false;
        }
    }

## 45.跳跃游戏II ##

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ - 2]

2、文章讲解：[代码随想录][Link 3]

3、题目：

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

*  输入: \[2,3,1,1,4\]
 *  输出: 2
 *  解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

说明: 假设你总是可以到达数组的最后一个位置。

4、视频链接：

[贪心算法，最少跳几步还得看覆盖范围 | LeetCode： 45.跳跃游戏II\_哔哩哔哩\_bilibili][_ LeetCode_ 45._II_bilibili]

5、思路：

本题相对于[55.跳跃游戏(opens new window)][55._opens new window]还是难了不少。

但思路是相似的，还是要看最大覆盖范围。

本题要计算最少步数，那么就要想清楚什么时候步数才一定要加一呢？

贪心的思路，局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最少步数。

思路虽然是这样，但在写代码的时候还不能真的能跳多远就跳多远，那样就不知道下一步最远能跳到哪里了。

**所以真正解题的时候，要从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最少步数！**

**这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖**。

如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。

如图：

![efcbb7e0d466976e288cd40de209165a.png][]

**图中覆盖范围的意义在于，只要红色的区域，最多两步一定可以到！（不用管具体怎么跳，反正一定可以跳到）**

#### 方法一 ####

从图中可以看出来，就是移动下标达到了当前覆盖的最远距离下标时，步数就要加一，来增加覆盖距离。最后的步数就是最少步数。

这里还是有个特殊情况需要考虑，当移动下标达到了当前覆盖的最远距离下标时

*  如果当前覆盖最远距离下标不是是集合终点，步数就加一，还需要继续走。
 *  如果当前覆盖最远距离下标就是是集合终点，步数不用加一，因为不能再往后走了。

#### 方法二 ####

依然是贪心，思路和方法一差不多，代码可以简洁一些。

**针对于方法一的特殊情况，可以统一处理**，即：移动下标只要遇到当前覆盖最远距离的下标，直接步数加一，不考虑是不是终点的情况。

想要达到这样的效果，只要让移动下标，最大只能移动到 nums.size - 2 的地方就可以了。

因为当移动下标指向 nums.size - 2 时：

*  如果移动下标等于当前覆盖最大距离下标， 需要再走一步（即 ans++），因为最后一步一定是可以到的终点。（题目假设总是可以到达数组的最后一个位置），如图：
    
    ![5ca758f6c5a447a3b7fbc2ba5ebdcde4.png][]
 *  如果移动下标不等于当前覆盖最大距离下标，说明当前覆盖最远距离就可以直接达到终点了，不需要再走一步。如图：

![0b6a16701d0dc25b1ddb0780b536d821.png][]

可以看出版本二的代码相对于版本一简化了不少！

**其精髓在于控制移动下标 i 只移动到 nums.size() - 2 的位置**，所以移动下标只要遇到当前覆盖最远距离的下标，直接步数加一，不用考虑别的了。

#### 总结 ####

相信大家可以发现，这道题目相当于[55.跳跃游戏(opens new window)][55._opens new window]难了不止一点。

但代码又十分简单，贪心就是这么巧妙。

理解本题的关键在于：**以最小的步数增加最大的覆盖范围，直到覆盖范围覆盖了终点**，这个范围内最少步数一定可以跳到，不用管具体是怎么跳的，不纠结于一步究竟跳一个单位还是两个单位。

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

[LeetCode_ -]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
[Link 1]: https://www.programmercarl.com/0122.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAII.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[LeetCode_122._II_bilibili]: https://www.bilibili.com/video/BV1ev4y1C7na
[c7a7d1616213590df42be4b1c102d03d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/059f932092714f989fefa281ee8acc4c.png
[LeetCode_ - 1]: https://leetcode.cn/problems/jump-game/
[Link 2]: https://www.programmercarl.com/0055.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8F.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[_ LeetCode_55._bilibili]: https://www.bilibili.com/video/BV1VG4y1X7kB
[b9a5a5294dec933a15b6080df61cf3af.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/bfaf11c2f4644b20863c97610b9c6382.png
[LeetCode_ - 2]: https://leetcode.cn/problems/jump-game-ii/
[Link 3]: https://www.programmercarl.com/0045.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8FII.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[_ LeetCode_ 45._II_bilibili]: https://www.bilibili.com/video/BV1Y24y1r7XZ
[55._opens new window]: https://programmercarl.com/0055.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8F.html
[efcbb7e0d466976e288cd40de209165a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/e69d8ff7f13843d1b37213468130f009.png
[5ca758f6c5a447a3b7fbc2ba5ebdcde4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/14e1e9fc4e964470bfa1e43960b830a6.png
[0b6a16701d0dc25b1ddb0780b536d821.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/20782e2ac8e04c528a9d4552c1671670.png