贪心理论
由局部最优推导到全局最优，这就是贪心的策略。
在什么时候使用贪心算法？可以试一试贪心，若无法证伪，则使用。
经典题目
455 分发饼干
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i](，)这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j]( )。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是满足尽可能多的孩子，并输出这个最大数值。
例子
输入: g = [1,2,3], s = [1,1] 输出: 1 解释: 你有三个孩子和两块小饼干，3 个孩子的胃口值分别是：1,2,3。 虽然你有两块小饼干，由于他们的尺寸都是 1，你只能让胃口值是 1 的孩子满足。 所以你应该输出 1。
思路
其实是一种模拟，有两种解法
- 要么大胃袋去找大饼干。
- 要么小饼干先满足小胃口。
sort默认是从小到大做排序的。
code
// 大胃袋去找大饼干
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int index = s.size() - 1;
int result = 0;
/* s should be greater than g */
for (int i = g.size() - 1; i >= 0; i--) {
if (index >= 0 && s[index] >= g[i]) {
result++;
index--;
}
}
return result;
}
};376 摆动序列
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
- 例如，
[1, 7, 4, 9, 2, 5]是一个 摆动序列 ，因为差值(6, -3, 5, -7, 3)是正负交替出现的。 - 相反，
[1, 4, 7, 2, 5]和[1, 7, 4, 5, 5]不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。
例子
输入：nums = [1,7,4,9,2,5] 输出：6 解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。
思路
既然允许从原始序列中删除一些，且原始数据的排序不能改变，那遇上不符合条件的数直接在循环里跳过就好了鸭。
code
typedef enum num_state_{
NULL_STATE_NUM,
POSITIVE_NUM,
NEGATIVE_NUM,
} num_state;
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if (nums.size() <= 1) {
return nums.size();
}
int res = 1;
int diff = 0;
int num_state = NULL_STATE_NUM;
for (int i = 1; i < nums.size(); i++) {
diff = nums[i] - nums[i - 1];
if (num_state == NULL_STATE_NUM) {
if (diff > 0) {
num_state = POSITIVE_NUM;
} else if (diff < 0) {
num_state = NEGATIVE_NUM;
} else {
continue;
}
res += 1;
}
if (num_state == POSITIVE_NUM) {
if (diff < 0) {
num_state = NEGATIVE_NUM;
res += 1;
} else {
continue;
}
} else {
if (diff > 0) {
num_state = POSITIVE_NUM;
res += 1;
} else {
continue;
}
}
}
return res;
}
};53 最大子序和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
例子
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
思路
贪心类的题目更多的是模拟。以及你需要知道局部最优是什么？在这一题里的局部最优就是：我们希望连续和越来越大，要取最大的，那么当连续出现负数的时候，这会阻挠我们取最大连续和，此时把连续和清空即可。
122 买卖股票的最佳时机II
理解题意，去做对应的转化，同一支股票买卖的最佳时机->最大利润，实际上我们可以从最小的一个个子区间集合而成，那我们要关注的是我的第n+1天比起第n天有没有利润。如果有利润把这个利润加上即可。
res += max(nums[i] - nums[i - 1], 0);- 跳跃游戏
这题怎么转化呢？其实就是算我们最大能力能走到哪个slot。所以我们在我们步长范围内去操作。
class Solution {
public:
bool canJump(vector<int>& nums) {
int ability_reach_index = 0;
int end = nums.size() - 1;
if (nums.size() == 1) return true;
for (int i = 0; i <= ability_reach_index; i++) {
ability_reach_index = max(i + nums[i], ability_reach_index);
if (ability_reach_index >= end)
return true;
}
return false;
}
};1005 k次取反后最大化的数组和
结合k的次数，把最大的k个负数反转过来，若k还有剩，则将最小的数反复翻转。
134 加油站
要走完这个环，有两个条件：
- 我们当前的油量要始终大于0
- 总的可取油量要大于所消耗的油量
根据这两个条件去做模拟即可
135 分发糖果
可以分两个层次去考虑
- 从左往右，已知左边的小孩分数，以lchild为基去比较rchild的分数
- 从右往左，已知右边小孩的分数，以rchild为基去比较lchild的分数
860 柠檬水找零
逻辑非常固定的一题，遇上20的先找10块和5块的即可。
406 根据身高重建队列
这一题理解题意花了半天，但是还是从两个维度去考虑，就不难得出结果。
先对身高排序，再按照身高从高到低的位置期望去插入。
452 用最少数量的箭引爆气球
如果一枝箭能射爆尽可能多的交集，那就设。
先排序，然后确定边界：如果两个气球完全不重合，也就是说 i-1的气球的右边界 与 i的左边界不重合，这时候就需要多射一枝箭了。
435 无重叠区间
与452相比，452是找重叠的，453是找不重叠的。减去即可。
763 划分字母区间
这题实际上是从总体角度去考虑了，没有贪心的思想。。
找到一个字母的最长的距离，把它记录下来。而后便利整个字符串，若下标和最长距离相等，那我们知道这就是一段被分割出来的结果了。
20 合并区间
没做，本质上还是判断区间重叠的问题。
968.监控二叉树
先不做咯
