摘要

• 今天的题目的共同点是从左到右遍历数组中的元素，记录会影响局部最优的那个元素的信息，从而影响到下一步的选择。
• 和动态规划比起来，不需要记录每个元素的信息，只需要记录会影响下一步的元素的信息即可。

LeetCode122 买卖股票的最佳时机

122. 买卖股票的最佳时机 II - 力扣（Leetcode）

• 每一步：根据prices[i - 1]和prices[i]的大小关系，决定第i - 1天是否买入股票并在第i天出售。
• 局部最优：prices[i - 1] < prices[i]，在第i天卖出股票有利润。
• 全局最优：得到的利润最大。

完整题解代码如下

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        if (prices.size() < 2) return profit;

        for (int i = 1; i < prices.size(); i++) {
            if (prices[i - 1] >= prices[i]) continue;
            else profit += prices[i] - prices[i - 1];
        }

        return profit;
    }
};

LeetCode55 跳跃游戏

55. 跳跃游戏 - 力扣（Leetcode）

• 将每个点（即数组的每个元素）扩展成对应可以跳跃到的区间，都是向右跳，所以再对可以跳跃到的点做扩展成可以跳跃到的区间的操作。

• 直到区间包括数组最后一位或者展开所有点都不能使区间包含数组最后一位。

• 这题的贪心选择策略，简单来说就是根据当前能跳跃到的范围从左到右，求每个位置能跳跃到的范围，并根据当前位置的范围来更新能跳跃到的范围。当能跳跃到的范围已经包含最后一个下标时，

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int cover = 0;
        for (int i = 0; i <= cover; i++) {
            cover = max(i + nums[i], cover);
            if (cover >= nums.size() - 1) return true;
        }
        return false;
    }
};

LeetCode45 跳跃游戏II

45. 跳跃游戏 II - 力扣（Leetcode）

• 和上一题的思路类似，也是将每个点展开成一个可以跳跃到的区间。
• 和上一题不同的是，这题需要统计跳跃的步数，所以不能每到一个位置都更新可以跳跃的到的区间。为了区分每一步跳跃，应该保存当前可以跳跃到的区间和下一步可以跳跃到的区间。实际上就记录了每一步跳跃能到达的区间。
• 以[2, 2, 1, 1, 4]为例

• 第一步，当i = 0时，计算出这一步可以跳跃到的区间为[0, 2]，所以当i在[0, 2]中移动时，都只算一步。并且，当i在[0, 2]中移动时，要根据每个位置记录下一步能到的最远距离。下一步的最远距离由i = 1或i = 2时取到，都是最远到i = 3。
• 第二步，当i = 2时，已经到达了第一步最远能跳到的位置，要再往下跳的话，需要多跳一步，并更新可以跳跃到的区间为[2, 3]，下一步能到的最远位置是i = 4。
• 第三步， 当i = 3，到达了第二步能最远能跳到的位置，要再往下跳，第三步能到达的最远位置是i = 4。到达数组最后一位

题解代码如下

class Solution {
public:
    int jump(vector<int>& nums) {
        int step = 0;
        int curCover = 0;
        int nextCover = 0;
        // 要注意循环终止的条件，到达数组最后一位就不用再跳了，所以i最大是nums.size()-2
        // 如果i < nums.size()，会多算一步，多算的一步就是在数组最后一位再往后跳
        for (int i = 0; i < nums.size() - 1; i++) {
            nextCover = max(i + nums[i], nextCover);
            if (i >= curCover) {
                curCover = nextCover;
                step++; 
            }
        }
        return step;
    }
};