目录

1  121. 买卖股票的最佳时机

2  55. 跳跃游戏

3  45. 跳跃游戏 II

4  763. 划分字母区间

---

菜鸟做题，语言是 C++

1  121. 买卖股票的最佳时机

解题思路：

• 维护一个变量 max_price
• max_price 用于存储排在 i 天之后的股票最高价格
• 第 i 天的最高利润 = max_price - 第 i 天的股票价格

思路说明：

假设股票价格数组为 [7，1，5，3，6，4]，从后往前遍历数组以计算 max_price，如下图所示。

1）如果第 i 天的股票价格低于 max_price，则

• 第 i 天的最高利润 = max_price - 第 i 天的股票价格
• 需要更新 profit
• 不需要更新 max_price

2）如果第 i 天的股票价格高于 max_price，则

• 第 i 天的最高利润 = 0
• 不需要更新 profit
• 需要更新 max_price

在如下代码中，我用的是变量 ans 代表 profit 的含义。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int ans = 0, max_price = 0;

        for (int i = n - 1; i >= 0; --i) {
            if (prices[i] > max_price) {
                max_price = prices[i];
            } else {
                ans = max(ans, max_price - prices[i]);
            }
        }

        return ans;
    }
};

2  55. 跳跃游戏

解题思路：

• 遍历 nums 数组
• 不断更新最远距离 maxDistance
• 如果 maxDistance >= nums.size() - 1，则返回 true

思路说明图：

1. 遍历第 0 个元素，maxDistance = 2
2. 遍历第 1 个元素，maxDistance = 1 + 3 = 4
3. 遍历第 2 个元素，maxDistance = 4（> 2 + 1）
4. 以此类推

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

3  45. 跳跃游戏 II

解题思路：

• 仍然是遍历 nums 数组，每次更新 maxDistance 范围
• 针对在同一次更新后被包含进去的位置，算作一次跳跃

思路说明图：

将 maxDistance 初始化为 0，被包含进去的 0 号位置，属于第一次跳跃（count = 0）。根据 0 号位置更新 maxDistance 为 2，被包含进去的 1、2 号位置，属于第二次跳跃（count = 1）。根据 1、2 号位置更新 maxDistance 为 4，被包含进去的 3、4 号位置，属于第三次跳跃（count = 2）。

如果更新 maxDistance 后发现 maxDistance >= nums.size() - 1，则返回 count + 1 即可。为什么是 count + 1？因为目前只是能够跳跃到达 nums.size() - 1，但还没有跳。

class Solution {
public:
    int jump(vector<int>& nums) {
        int maxDistance = 0;
        int pos = 0, count = 0;

        if (pos >= nums.size() - 1)
            return 0;

        while (pos < nums.size()) {
            int temp = maxDistance;
            while (pos <= temp) {
                maxDistance = max(maxDistance, pos + nums[pos]);
                if (maxDistance >= nums.size() - 1) {
                    return count + 1;
                }
                ++pos;
            }
            ++count;
        }

        return count;
    }
};

4  763. 划分字母区间

解题思路：

• 遍历字符串 s，记录每个字母的最后出现位置
• 设置 begin = 0，即从 0 号字母开始划分字符串
• 根据每个字母的最后出现位置不断更新 end
• 若当前位置 = end，则 begin ~ end 之间是一个子串

思路说明图：

• 图中的 B 代表 begin，即子串的开头；E 代表 end，即子串的结尾
• 初始化 begin 为 0，初始化 E 为第一个字母的最后出现位置

我们需要保证的是 B 和 E 之间的所有字母不能横跨两个子串。换句话说，B 和 E 之间的 b 和 c 的最后出现位置不能超过 a 的最后出现位置 E 。如果超过了，我们需要更新 E 。

第一轮：首先访问 a，并且设置 E 为 a 的最后出现位置；接着访问 b，由于 b 的最后出现位置没有超过 E，因此不需要更新 E。以此类推访问到 c，由于 c 的最后出现位置没有超过 E，因此不需要更新 E 。最后指针 i 移动到 E，说明 B 和 E 之间的字母只会出现在该区间内，由此得到第一个子串。

第二轮：B 更新到 E 的后面一个位置，模仿第一轮的操作继续访问。

由于篇幅有限，因此图中省略了一些步骤，请自行脑补。

class Solution {
public:
    vector<int> partitionLabels(string s) {
        unordered_map<char, int> charEnd;
        for (int i = 0; i < s.size(); ++i) {
            charEnd[s[i]] = i;
        }

        vector<int> ans;
        int begin = 0, end = 0;
        for (int i = 0; i < s.size(); ++i) {
            end = max(end, charEnd[s[i]]);
            if (i == end) {
                ans.push_back(end - begin + 1);
                begin =  end + 1;
            }
        }

        return ans;
    }
};

上述代码用的是哈希表 charEnd 来存储字母的最后出现位置，换成 vector<int> 也行。

这样做会超出内存限制：

int subStrEnd = charEnd[s[0]];
while (begin < s.size()) {
    while (end <= subStrEnd) {
        subStrEnd = max(subStrEnd, charEnd[s[end]]);
        ++end;
    }
    ans.push_back(end - begin);
    begin = end;
}