leetcode-hot-100 (贪心算法）

1、买卖股票的最佳时机

题目链接：买卖股票的最佳时机
题目描述：给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

解答

详见我之前写的博客：股票问题汇总

超时代码：使用双指针进行两次遍历，时间复杂度为 $O(n^2)$
正确解法：从左向右遍历数组，每次记录出现的最小值，然后使用遍历到的位置减去之前存储的最小值即可。

2、跳跃游戏

题目链接：跳跃游戏
题目描述：给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

解答

贪心（官方解答）

class Solution {
public:bool canJump(vector<int>& nums) {int len = nums.size(); // 数组长度int maxPos = 0;        // 初始位置for (int i = 0; i < len; i++) {// 表示位置 i 能到达if (i <= maxPos) {// 更新能到达的最远地方maxPos = max(maxPos, i + nums[i]);// 最远地方超过了数组长度，返回 true 即可if (maxPos >= len - 1)return true;}}// 数组遍历完了，都没有到末尾，表示到不了末尾；return false;}
};

3、跳跃游戏 II

题目链接：跳跃游戏 II
题目描述：给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：0 <= j <= nums[i] 且 i + j < n
返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。

解答

方法一：动态规划

不是我说，动态规划是真好用，即每次都找到优化子结构，然后逐步向后优化。

class Solution {
public:int jump(vector<int>& nums) {int n = nums.size();vector<int> dp(n, INT_MAX);dp[0] = 0;for (int i = 0; i < n; i++) {for (int j = i + 1; j < i + nums[i]; j++)dp[j] = min(dp[j], dp[i] + 1);}return dp[n - 1];}
};

思路还是很简单的，但是对于这道题目的话，时间复杂度还是比较高的（$O(N^2)$），因此肯定还是有可以进行优化的地方。不妨试试贪心？

方法二：贪心（从前向后）

实际上我觉得这个思想和方法一的动态规划的区别不是很大。

从初始位置 0 开始，我们维护一个当前跳跃能够到达的最远范围，称为「覆盖范围」。这个范围的右边界记为 end，表示在不增加跳跃次数的情况下，能够到达的最远下标。
在遍历数组的过程中，我们同时维护一个 max_Pos 变量，用于记录在当前覆盖范围内所有位置所能跳到的最远位置。

那么，何时需要进行跳跃、扩展覆盖范围呢？

答案是：当遍历到当前覆盖范围的右边界 end 时，如果仍未到达数组末尾，说明必须进行一次新的跳跃，才能继续前进。此时，我们将覆盖范围扩展到 max_Pos，并令 end = max_Pos，同时跳跃次数 step 加 1。
这个过程不断重复，直到 max_Pos >= n - 1，即覆盖范围已经包含数组的最后一个位置 n - 1。
需要注意的是，我们只需遍历到 n - 2，因为一旦到达或超过 n - 1，任务就已经完成，无需再从最后一个位置进行跳跃。

那上述具体贪在哪里呢？
贪心体现在：每一步都选择在当前覆盖范围内能跳到最远位置的策略，局部最优解直接构成全局最优解。

class Solution {
public:int jump(vector<int>& nums) {int step = 0, max_Pos = 0, end = 0;int n = nums.size();for (int i = 0; i < n - 1; i++) {if (i <= max_Pos) {max_Pos = max(max_Pos, i + nums[i]);if (i == end) {end = max_Pos;step++;}}}return step;}
};

方法三：贪心（从后向前）

我们的目标是到达数组的最后一个位置。考虑最后一步跳跃的起点，它必须满足：从该位置能够直接跳至末尾（即 i + nums[i] >= n - 1）。如果有多个这样的位置，我们应贪心地选择下标最小的那个，因为它距离终点最远，意味着用更少的跳跃步数覆盖了更多区域。
因此，我们可以从左到右遍历数组，找到第一个满足 i + nums[i] >= n - 1 的位置，作为最后一步跳跃的起点。然后将问题递归地转化为：从起点跳到这个新位置的最少步数。重复此过程，直到当前位置为 0。

贪心策略体现在：每一步都选择能到达当前终点的最靠前（下标最小）的位置作为上一跳的起点，从而保证跳跃次数最少。

class Solution {
public:int jump(vector<int>& nums) {int pos = nums.size() - 1;int step = 0; // 记录跳跃的总次数while (pos > 0) {for (int i = 0; i < pos; i++) {// 贪在此处：从前向后找，找到最前面能跳到指定位置的值if (pos <= i + nums[i]) {pos = i;step++;break;}}}return step;}
};

4、 划分字母区间

题目链接：划分字母区间
题目描述：
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

解答

贪心

思路我还是能想到，但是具体的实现还是不是很会，还是需要不断地学习。
这道题感觉是上一题 跳跃游戏II 的应用题，只是将这个跳跃位置换成了字母。
我试着翻译一下这道题目：
从起始位置（即数组的第一个元素）出发，向后查找与起始元素相同字符的最后一个出现位置，确定一个初始区间。然后，在该区间内遍历每一个位置，尝试扩展区间的右边界——即根据当前区间内每个位置所能到达的最远位置（类似于跳跃游戏中的最大可达下标），不断更新区间的覆盖范围，直到右边界无法再扩展。这样就划分出来了一个字母区间。

这题的难点
关键在于如何高效确定区间的最右边界。如果对每个字符都从头遍历字符串去寻找其最后一次出现的位置，会导致在扩展区间时重复扫描，时间复杂度较高。

更优的做法是：预先使用一个数组记录每个字符在字符串中最后一次出现的下标。这样，在后续遍历过程中，我们可以将每个位置的“最远可达边界”直接视为 i + (该字符最后出现的位置)，从而将问题转化为类似“跳跃游戏”的模型——每一步尽可能扩展覆盖范围。

这样就转化为了上面 跳跃游戏II 的问题了。

class Solution {
public:vector<int> partitionLabels(string s) {int last[26];int len = s.size();// 存储26个字母在数组中最后出现的位置，为后续右边界的确定铺路for (int i = 0; i < len; i++)last[s[i] - 'a'] = i;vector<int> partition;int start = 0;int end = 0;for (int i = 0; i < len; i++) {// 确定一个初始区间end = max(end, last[s[i] - 'a']);// 要是到达了区间右边界，说明划分出来了一个区间if (i == end) {partition.push_back(end - start + 1);// 从下一个位置再确定新区间start = end + 1;}}return partition;}
};