说实话贪心算法并没有固定的套路。
所以唯一的难点就是如何通过局部最优，推出整体最优
最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。
靠自己手动模拟，如果模拟可行，就可以试一试贪心策略，如果不可行，可能需要动态规划。
贪心一般解题步骤
贪心算法一般分为如下四步：
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
其实这个分的有点细了，真正做题的时候很难分出这么详细的解题步骤，可能就是因为贪心的题目往往还和其他方面的知识混在一起
455.分发饼干
总结：从代码中可以看出我用了一个index来控制饼干数组的遍历，遍历饼干并没有再起一个for循环，而是采用自减的方式，这也是常用的技巧
判断条件 一直写错，for循环和if循环。写完多看看。
// 时间复杂度：O(nlogn) // 空间复杂度：O(1)
class Solution {
public:
int findContentChildren(vector& g, vector& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int index = s.size() - 1; // 饼干数组的下标
int result = 0;
for (int i = g.size() - 1; i >= 0; i--) {
if (index >= 0 && s[index] >= g[i]) {
result++;
index--;
}
}
return result;
}
};
376. 摆动序列
比较 当前是否相减等于正负，只要满足前后对比不同就行，中间连续递增或者递减都不符合。直接跳过。
总结： for （nums.size() - 1) 负判断 有一个《 = 0
class Solution {
public:
int wiggleMaxLength(vector& nums) {
if (nums.size() <= 1) return nums.size();
int curDiff = 0; // 当前一对差值
int preDiff = 0; // 前一对差值
int result = 1; // 记录峰值个数，序列默认序列最右边有一个峰值
for (int i = 0; i < nums.size() - 1; i++) {
curDiff = nums[i + 1] - nums[i];
// 出现峰值
if ((curDiff > 0 && preDiff <= 0) || (preDiff >= 0 && curDiff < 0)) {
result++;
preDiff = curDiff;
}
}
return result;
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(1)
53. 最大子序和
暴力解法的思路，第一层for 就是设置起始位置，第二层for循环遍历数组寻找最大值
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
class Solution {
public:
int maxSubArray(vector& nums) {
int result = INT32_MIN;
int count = 0;
for (int i = 0; i < nums.size(); i++) { // 设置起始位置
count = 0;
for (int j = i; j < nums.size(); j++) { // 每次从起始位置i开始遍历寻找最大值
count += nums[j];
result = count > result ? count : result;
}
}
return result;
}
};
贪心 缩小范围。
- 时间复杂度：O(n)
- 空间复杂度：O(1)
- 也会理解 为什么 result 要初始化为最小负数了。
class Solution {
public:
int maxSubArray(vector& nums) {
int result = INT32_MIN;
int count = 0;
for (int i = 0; i < nums.size(); i++) {
count += nums[i];
if (count > result) { // 取区间累计的最大值（相当于不断确定最大子序终止位置）
result = count;
}
if (count <= 0) count = 0; // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
}
return result;
}
};
122.买卖股票的最佳时机II
此时就是把利润分解为每天为单位的维度，而不是从0天到第3天整体去考虑！
其实我们需要收集每天的正利润就可以，收集正利润的区间，就是股票买卖的区间，而我们只需要关注最终利润，不需要记录区间。
那么只收集正利润就是贪心所贪的地方！
prices[i] - prices[i - 1] 奇诡 prices[i + 1] - prices[i] 不可以，开始从第3个开始了。
class Solution {
public:
int maxProfit(vector& prices) {
int result = 0;
for (int i = 1; i < prices.size(); i++) {
result += max(prices[i] - prices[i - 1], 0);
}
return result;
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(1)
55. 跳跃游戏
总结：不用纠结在哪最大几步，贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。
for (int i = 0; i <= cover; i++) { // 注意这里是小于等于cover
cover = max(i + nums[i], cover);
class Solution {
public:
bool canJump(vector& nums) {
int cover = 0;
if (nums.size() == 1) return true; // 只有一个元素，就是能达到
for (int i = 0; i <= cover; i++) { // 注意这里是小于等于cover
cover = max(i + nums[i], cover);
if (cover >= nums.size() - 1) return true; // 说明可以覆盖到终点了
}
return false;
}
};
45.跳跃游戏II
总结 ：
小标加上元素的内容，是框框覆盖的最远距离。
class Solution {
public:
int jump(vector& nums) {
int curDistance = 0; // 当前覆盖的最远距离下标
int ans = 0; // 记录走的最大步数
int nextDistance = 0; // 下一步覆盖的最远距离下标
for (int i = 0; i < nums.size() - 1; i++) { // 注意这里是小于nums.size() - 1，这是关键所在
nextDistance = max(nums[i] + i, nextDistance); // 更新下一步覆盖的最远距离下标
if (i == curDistance) { // 遇到当前覆盖的最远距离下标
curDistance = nextDistance; // 更新当前覆盖的最远距离下标
ans++;
}
}
return ans;
}
};
