1、买卖股票的最佳时机
题目链接：买卖股票的最佳时机
题目描述：给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
解答
详见我之前写的博客：股票问题汇总
超时代码：使用双指针进行两次遍历，时间复杂度为 O ( n 2 ) O(n^2) O(n2)
正确解法：从左向右遍历数组，每次记录出现的最小值，然后使用遍历到的位置减去之前存储的最小值即可。
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 ) O(N^2) O(N2)），因此肯定还是有可以进行优化的地方。不妨试试贪心？
方法二：贪心（从前向后）
实际上我觉得这个思想和方法一的动态规划的区别不是很大。
从初始位置 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;
}
};