代码随想录算法训练营第三十二天 | 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%E…
视频讲解：https://www.bilibili.com/video/BV1ev4y1C7na

思路

计算每天股票价格的差值，将正数加起来。

代码

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

分析：时间复杂度：O(n)，空间复杂度：O(1)。

55. 跳跃游戏

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

思路

• 通过遍历数组，判断从起点开始每个点的覆盖范围有没有覆盖到终点，如果有的话就返回true。
• 一开始cover的范围是0，随着数组的遍历而增加。
• 覆盖范围一直维持一个最大值。

cover = Math.max(i + nums[i], cover);

代码

class Solution {
    public boolean canJump(int[] nums) {
        if (nums.length == 1) return true;
        int cover = 0;
        for (int i = 0; i <= cover; i++) {
            cover = Math.max(i + nums[i], cover);
            if (cover >= nums.length - 1) return true; // 终点的距离是nums.length - 1
        }
        return false;
    }
}

分析：时间复杂度：O(n)，空间复杂度：O(1)。

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
视频讲解：https://www.bilibili.com/video/BV1Y24y1r7XZ

思路

• 记录走了几步覆盖到了终点。这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。

代码

class Solution {
    public int jump(int[] nums) {
        if (nums.length == 1) return 0;
        int curCover = 0, nextCover = 0, res = 0;
        for (int i = 0; i < nums.length; i++) {
            nextCover = Math.max(i + nums[i], nextCover);
            if (i == curCover) { // 已经走到了当前覆盖范围的最后
                if (curCover != nums.length - 1) { // 当前覆盖范围还没到终点，就再走一步
                    curCover = nextCover;
                    res++;
                    if (curCover >= nums.length - 1) break;
                } else break; // 当前覆盖范围覆盖到终点，得到最终结果
            } 
        }
        return res;
    }
}

分析：时间复杂度：O(n)，空间复杂度：O(1)。