👂 ▶ 逍遥叹 - 胡歌&沈以城【Mashup】 (163.com)
👂 庐州月 - 许嵩 - 单曲 - 网易云音乐
2.7 小时，加上写博客，4 道题，😂 -- 希望二刷时，可以 3 小时，8 道题....
目录
🍉买卖股票的最佳时机
🌼跳跃游戏
🍓跳跃游戏 II
🎂划分字母区间
🍉买卖股票的最佳时机
121. 买卖股票的最佳时机 - 力扣（LeetCode）
贪心：维护目前为止的最小值
class Solution {
public:
int maxProfit(vector<int>& prices) {
int minPrice = 1e4; // 维护一个最小值
int ans = 0;
for (auto x : prices) {
minPrice = min(minPrice, x);
ans = max(ans, x - minPrice);
}
ans = ans < 0 ? 0 : ans;
return ans;
}
};🌼跳跃游戏
55. 跳跃游戏 - 力扣（LeetCode）
贪心：维护可以跳到的最大索引（下标）
class Solution {
public:
bool canJump(vector<int>& nums) {
int Max = 0; // 维护当前可以跳到的最远下标
for (int i = 0; i < nums.size(); ++i) {
// 当前索引 i > Max, 说明无法到达
if (i > Max)
return false;
if (Max >= nums.size() - 1)
break;
Max = max(Max, i + nums[i]);
}
return true;
}
};
// 1 2 5 1 1 0 3 1 0 1 1 1🍓跳跃游戏 II
45. 跳跃游戏 II - 力扣（LeetCode）
题目保证 “可以到达 nums[n - 1]”
每次跳跃前，先计算最大范围，然后依次计算这个范围内
各个坐标所能到达的最远的点 maxPos，作为本次跳跃的目的地 end....
class Solution {
public:
int jump(vector<int>& nums) {
int maxPos = 0; // 维护最远的点
int ans = 0, end = 0;
// 不是 < nums.size(), 最后一个元素不用继续跳了
for (int i = 0; i < nums.size() - 1; ++i) {
// 最大范围 [i, end]
maxPos = max(maxPos, i + nums[i]); // 维护最远距离
if (i == end) { // 这一跳结束
end = maxPos;
ans++; // 只有到达 end, 才更新步数
}
}
return ans;
}
};
// 1 1
// 1🎂划分字母区间
763. 划分字母区间 - 力扣（LeetCode）
第一次遍历 O(n)，用一个数组 last[26] 维护每个字母最后出现的位置
当前子串范围 [start, end]
第 2 次遍历 O(n)，逐个遍历 i
动态地用 last[s[i] - 'a'] 更新 end，直到 i == end，满足当前子串要求
class Solution {
public:
vector<int> partitionLabels(string s) {
vector<int> ans;
int last[26];
for (int i = 0; i < s.size(); ++i)
last[s[i] - 'a'] = i; // 字母 s[i] 最后出现位置
int start = 0, end = 0; // 当前划分范围
for (int i = 0; i < s.size(); ++i) {
end = max(end, last[s[i] - 'a']); // 更新最后出现位置
if (i == end) {
ans.push_back(end - start + 1);
start = end + 1;
}
}
return ans;
}
};
