29、第八章 贪心算法 part02

本节内容

• 122.买卖股票的最佳时机II
• 55. 跳跃游戏
• 45.跳跃游戏II

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

建议：本题解法很巧妙，大家可以看题思考一下，在看题解。

题目链接： https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
文章讲解： https://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
视频讲解：

题目分析

方案一：贪心

一直记录上升区间

class Solution {
    public int maxProfit(int[] prices) {
        int result = 0;
        int left = 0, right = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] >= prices[right]){
                right = i;
            } else {
                result += prices[right] - prices[left];
                right = i;
                left = i;
            }
        }
        result += prices[right] - prices[left]; // 最后一段一直上升，没有对其进行计算
        return result;
    }
}

结果

解答成功:
执行耗时:1 ms,击败了70.69% 的Java用户
内存消耗:43.3 MB,击败了26.75% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( 1 )

方案二：动态规划

class Solution {
    public int maxProfit(int[] prices) {
        int[] dp = new int[prices.length];

        dp[0] = 0;

        for (int i = 1; i < prices.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 1] + prices[i] - prices[i - 1]);
        }
        return dp[dp.length - 1];
    }
}

结果

解答成功:
执行耗时:1 ms,击败了70.69% 的Java用户
内存消耗:43.3 MB,击败了27.68% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( n )

代码随想录

https://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

思路

本题首先要清楚两点：

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

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

贪心算法

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

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

如何分解呢？

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

如图：

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

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

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

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

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

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

对应 C++代码如下：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int result = 0;
        for (int i = 1; i < prices.size(); i++) {
            result += max(prices[i] - prices[i - 1], 0);
        }
        return result;
    }
};

• 时间复杂度：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(prices[i] - prices[i - 1], 0);
        }
        return result;
    }
}

动态规划

动态规划将在下一个系列详细讲解

• 时间复杂度：O(n)
• 空间复杂度：O(n)

股票问题其实是一个系列的，属于动态规划的范畴，因为目前在讲解贪心系列，所以股票问题会在之后的动态规划系列中详细讲解。

可以看出有时候，贪心往往比动态规划更巧妙，更好用，所以别小看了贪心算法。

本题中理解利润拆分是关键点！ 不要整块的去看，而是把整体利润拆为每天的利润。

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

代码实现

class Solution { // 动态规划
    public int maxProfit(int[] prices) {
        // [天数][是否持有股票]
        int[][] dp = new int[prices.length][2];

        // base case
        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        for (int i = 1; i < prices.length; i++) {
            // dp公式
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }

        return dp[prices.length - 1][0];
    }
}

55. 跳跃游戏※

建议：本题如果没接触过，很难想到，所以不要自己憋时间太久，读题思考一会，没思路立刻看题解

题目链接： https://leetcode.cn/problems/jump-game/
文章讲解： https://programmercarl.com/0055.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8F.html
视频讲解：

题目分析

方案一：回溯

尝试通过回溯去做，其时间复杂度较高，虽然进行了一定的剪枝操作，但是其最坏情况的时间复杂度是存在的，然后题解中刚好有这这种情况，直接运行超时。

class Solution {
    public boolean canJump(int[] nums) {
        return backtracking(nums, 0);

    }
    private boolean backtracking(int[] nums, int index) {
        if (index >= nums.length - 1) return true;
        if (nums[index] == 0) return false;

        for (int i = nums[index]; i > 0; i--) {
            if (backtracking(nums, index + i)) return true;
        }
        return false;
    }
}

结果

Time Limit Exceeded

[9997,9997,9996,9995,9994,……,4,3,2,1,0,0]

分析

时间复杂度：
O( n! )

空间复杂度：
O( n )

方案二

从后向前遍历，只有遇到0的时候才去采取特殊的措施。

遇到0之后，就开始判断前面的数据是否可以正常跳过此点，如果可以找到就接着去找0

class Solution {
    public boolean canJump(int[] nums) {
        boolean notJump = false; // 当没有遇到0的时候为false
        int index = 0; // 记录数值为0的坐标值
        for (int i = nums.length - 2; i >= 0; i--) {
            if (!notJump && nums[i] == 0) {
                notJump = true;
                index = i;
            }
            if (notJump) {
                if (i + nums[i] > index){
                    notJump = false;
                }
            }
        }
        return !notJump;
    }
}

结果

解答成功:
执行耗时:1 ms,击败了99.82% 的Java用户
内存消耗:42.8 MB,击败了42.08% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( 1 )

代码随想录

https://programmercarl.com/0055.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8F.html

思路

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

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

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

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

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

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

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

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

如图：

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

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

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

C++代码如下：

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int cover = 0;
        if (nums.size() == 1) return true; // 只有一个元素，就是能达到
        for (int i = 0; i <= cover; i++) { // 注意这里是小于等于cover
            cover = max(i + nums[i], cover);
            if (cover >= nums.size() - 1) return true; // 说明可以覆盖到终点了
        }
        return false;
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(1)

总结

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

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

贪心系列，题目和题目之间貌似没有什么联系？

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

代码实现

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(coverRange, i + nums[i]);
            if (coverRange >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }
}

45.跳跃游戏II※

建议：本题同样不容易想出来。贪心就是这样，有的时候 会感觉简单到离谱，有时候，难的不行，主要是不容易想到。

题目链接： https://leetcode.cn/problems/jump-game-ii/
文章讲解： https://programmercarl.com/0045.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8FII.html
视频讲解：

题目分析

方案一

class Solution {
    public int jump(int[] nums) {
        int result = 0;

        for (int index = 0; index < nums.length - 1; ) {
            index = findNextIndex(nums, index);
            result++;
        }

        return result;
    }

    private int findNextIndex(int[] nums, int index) {
        if (index + nums[index] >= nums.length - 1) return index + nums[index];
        int temp = 0, tempIndex = 0;

        for (int i = 1; i < nums[index]; i++) { // 找出最大的坐标
            if (nums[index + i] + i >= temp) {
                temp = nums[index + i] + i;
                tempIndex = index + i;
            }
        }

        if (tempIndex + nums[tempIndex] > index + nums[index] + nums[index + nums[index]]) return tempIndex;
        return nums[index] + index;
    }
}

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:43.7 MB,击败了22.48% 的Java用户

分析

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

空间复杂度：
O( 1 )

代码随想录

https://programmercarl.com/0045.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8FII.html

思路

本题相对于 55.跳跃游戏 还是难了不少。

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

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

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

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

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

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

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

如图：

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

方法一

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

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

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

C++代码如下：（详细注释）

// 版本一
class Solution {
public:
    int jump(vector<int>& nums) {
        if (nums.size() == 1) return 0;
        int curDistance = 0;    // 当前覆盖最远距离下标
        int ans = 0;            // 记录走的最大步数
        int nextDistance = 0;   // 下一步覆盖最远距离下标
        for (int i = 0; i < nums.size(); i++) {
            nextDistance = max(nums[i] + i, nextDistance);  // 更新下一步覆盖最远距离下标
            if (i == curDistance) {                         // 遇到当前覆盖最远距离下标
                ans++;                                  // 需要走下一步
                curDistance = nextDistance;             // 更新当前覆盖最远距离下标（相当于加油了）
                if (nextDistance >= nums.size() - 1) break;  // 当前覆盖最远距到达集合终点，不用做ans++操作了，直接结束
            }
        }
        return ans;
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(1)

代码实现

// 版本一
class Solution {
    public int jump(int[] nums) {
        if (nums == null || nums.length == 0 || nums.length == 1) {
            return 0;
        }
        //记录跳跃的次数
        int count=0;
        //当前的覆盖最大区域
        int curDistance = 0;
        //最大的覆盖区域
        int maxDistance = 0;
        for (int i = 0; i < nums.length; i++) {
            //在可覆盖区域内更新最大的覆盖区域
            maxDistance = Math.max(maxDistance,i+nums[i]);
            //说明当前一步，再跳一步就到达了末尾
            if (maxDistance>=nums.length-1){
                count++;
                break;
            }
            //走到当前覆盖的最大区域时，更新下一步可达的最大区域
            if (i==curDistance){
                curDistance = maxDistance;
                count++;
            }
        }
        return count;
    }
}

方法二

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

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

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

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

• 如果移动下标等于当前覆盖最大距离下标， 需要再走一步（即 ans++），因为最后一步一定是可以到的终点。（题目假设总是可以到达数组的最后一个位置），如图：

• 如果移动下标不等于当前覆盖最大距离下标，说明当前覆盖最远距离就可以直接达到终点了，不需要再走一步。如图：

代码如下：

// 版本二
class Solution {
public:
    int jump(vector<int>& nums) {
        int curDistance = 0;    // 当前覆盖的最远距离下标
        int ans = 0;            // 记录走的最大步数
        int nextDistance = 0;   // 下一步覆盖的最远距离下标
        for (int i = 0; i < nums.size() - 1; i++) { // 注意这里是小于nums.size() - 1，这是关键所在
            nextDistance = max(nums[i] + i, nextDistance); // 更新下一步覆盖的最远距离下标
            if (i == curDistance) {                 // 遇到当前覆盖的最远距离下标
                curDistance = nextDistance;         // 更新当前覆盖的最远距离下标
                ans++;
            }
        }
        return ans;
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(1)

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

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

总结

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

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

代码实现

// 版本二
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;
    }
}