力扣hot100 -- 贪心算法

👂 ▶ 逍遥叹 - 胡歌&沈以城【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;}
};