贪心算法总结
贪心理论基础
很贪心，没有固定的套路。总的来说，如果找出局部最优并可以推出全局最优，就是贪心，如果局部最优都没找出来，就不是贪心，可能是单纯的模拟。
有时候，贪心也是对暴力解法的优化。
考虑暴力解法的本质，如何去简化暴力解法。
简单题
分发饼干
大饼干优先满足大孩子（后序遍历）。或者是用小饼干先满足小孩子（前序遍历）。本质上是用合适的饼干喂养合适的孩子。不要出现饼干上的浪费。
K次取反后最大化数组和
局部最优是让绝对值大的负数变为正数。如果所有的负数都变为了正数，K还有剩余，那么就找一个。反复变换数值最小的元素，将 K 次消耗满。
柠檬水找零
维护三种钞票的数量。对，因为10美元只能给账单20找零，而5美元可以给账单10和账单20找零5美元，更万能。因此，因此，在找零时应该优先消耗10美元钞票，最后再消耗更加万能的5美元钞票。
贪心中等题
摆动序列
贪心的思路
这道题关键是要统计峰值点。如果出现峰值，才增加计数。这个时候就需要考虑出现峰值的情况了。
有三种情况：1 正常峰值2 上下坡中有平坡3 单调中平坡。因为出现峰值需要前面有一个，后面有一个值。最少需要三个键，
所以考虑到左右边界。左边界在前面增加一个差为0，i从第一个数遍历。右边界不遍历，直接在result上+1或者result从1开始累加。
递归思路
关键要理解，上升摆动序列长度的增加，依赖于下降摆动序列的长度。下降摆动序列长度的增加依赖于上升摆动序列的长度。
for (int i = 1; i < nums.size(); i++) {
if (nums[i] > nums[i - 1]) {
// 上升：可以在之前下降序列基础上+1
up = down + 1;
} else if (nums[i] < nums[i - 1]) {
// 下降：可以在之前上升序列基础上+1
down = up + 1;
}
// 如果相等，up和down都不变
}单调递增数字
从后向前遍历。一旦出现前一个数字大于当前数字，那么就将前一个数字减1；然后从当前数字往后全部赋值为9。
贪心股票问题
股票问题除了能用动态规划，有时候也可以从贪心的角度解决。
买卖股票的最佳时机II(多次买卖)
主要需要想到把最终的利益分解成每天的利益，那么只要每天的利益最大（局部最优），总体利益（全局最优）最大。如果当天相对于前一天股票价格是上涨的，那么就应该前一天买，当天卖。这样的话，就可以达到每天的利益最优，也就是每天的利益是正。
买卖股票的最佳时机含手续费
贪心思路
对于上一道题，不用关心具体什么时候买卖，只要每天的利益是正的就可以了。
但是有了手续费，就需要关心什么时候买卖了。因为计算所获得的利润需要考虑买卖后的利润是否足以支撑这个手续费的情况。
贪心的策略就是低值买、高值卖。如果算上手续费还盈利，就卖。
但是同时保持一个最低买入价的概念，准备随时重新买入。
因为并不是像前一天买、后一天卖这样简单，有可能会出现几天的挣利加起来才满足手续费。因此，买入日期和卖入日期就不是差一天了。
所以就必须要找到具体的买入日期和卖出日期。
首先维护一个动态的买入价，设为第一天的价格。遇到更低价格时，更新买入价。
卖出时机判断的话，就需要判断当天的价格是否大于买入价加上手续费。如果是，就立即卖出，累计利润。并重新设置买入价。如果发现更低的价格，则更新买入价。如果发现相同的价格，就啥也不做，不买也不卖。
int maxProfit(vector<int>& prices, int fee) {
int n = prices.size();
int buy = prices[0]; // 当前的买入价格
int profit = 0; // 总利润
for (int i = 1; i < n; i++) {
// 如果当前价格比买入价高，且能覆盖手续费，就卖出
if (prices[i] > buy + fee) {
profit += prices[i] - buy - fee;
buy = prices[i] - fee; // 重新设置买入价（减去手续费，相当于为下次交易做准备）
}
// 如果发现更低的价格，更新买入价
else if (prices[i] < buy) {
buy = prices[i];
}
}
return profit;
}两个维度权衡问题
分发糖果
孩子的糖果数量取决于本身和左孩子和右孩子的相对评分情况。
贪心的话就是说，如果相邻的孩子糖果数量大的话，应该只多一个糖果就可以。
局部最优：
每次只关注相邻的两个孩子
确保评分高的比评分低的多1个糖果（最少的额外糖果）
但是因为要考虑本身和左孩子的评分大小，以及和右孩子的评分大小，因此是不能一次遍历同时满足左右两个方向的约束，所以要分别处理！
先从左向右处理右孩子比左孩子评分高的情况，再从右向左处理左孩子比右孩子评分高的情况。
在从右到左遍历的过程中，一个关键点是，如果左孩子比右孩子评分高，那么左孩子的评分应该是他本身的评分和右孩子评分 + 1 这两个之中的最大值，这样才不会破坏掉第一次遍历处理好的已有的约束。
根据身高重建队列
队列的顺序取决于身高和前面有多少个身高高于他的人--K值。两个维度，因此对于两个维度的题目，一定要想好如何确定一个维度，然后再按照另一个维度重新排列。
贪心难题
区间问题
跳跃游戏
要求能否跳到最后一个位置，本质上是要不断更新最大可覆盖范围。
如果可覆盖范围覆盖到了终点，那么就可以到达最后一个位置。
贪心贪的是每次跳跃都使得覆盖范围保持最大。表现形式上看，是维护一个最大可覆盖范围。本质上，过程模拟的话是说：
假如当前为止，我可以跳5步。
那么，如果这5步中我跳1步，覆盖范围反而没有原来的覆盖范围大，例如为2步，那么我就不跳。
如果我跳一步、跳两步或跳三步，跳到的位置覆盖范围反而变大了，那么我就跳相应的步数。这样做到，始终维护一个最大的可覆盖范围，即始终能够跳得更远。
跳跃游戏II
跳跃游戏2要求使用最少次数到达终点。要求是一定可以到达终点，那么最少步数就要求每次选择步数能够使得覆盖范围得到最大的扩张。
也就是说，要跳每次选的步数都能够使下一步跳的范围更大。
本质上，贪心贪的是下一步的覆盖范围。
用最少数量的箭引爆气球
局部最优：尽可能找多气球的公共区域在一起射气球。
这个过程就是对气球区间进行排序，可以按照起始位置或者按照终止位置排序。然后判断当前区间与上一个区间是否重叠。
如果重叠的话，箭的数量就不用加1，然后更新重叠区间；如果不重叠的话，箭的数量就要加1，然后更新重叠区间（当前区间作为新的重叠区间）。
无重叠区间
本质上是要找重叠区间，然后移除重叠区间，累计移除的个数。假设按照起始位置排序。
在判断重叠区间时，贪心策略指的是每次遇到重叠时，需要移除区间（result++），然后更新重叠区间（或者说选择移除哪个区间）的话，优先保留右端点更小的区间。这样更不容易与右后边的区间重叠。
划分字母区间
寻找分割点，同时记录每个区间的边界。
从头遍历每一个字母，并且更新已经遍历到的字母所能达到的最远边界。
当下标达到最远边界的时候，该下标就是分割点。记录区间长度，并且更新区间左端点。
其实，这道题和重叠区间性质是一样的。
每个字母第一次出现的位置和最后出现的位置可以映射为每个字母都有一个区间。题目要求每个字母只能出现在一个区间里，要求我们划分尽可能多的片段，也就是说要使得重叠区间尽可能少。
合并区间
新建一个重叠区间的结果数组，然后按照左边界排序，从左向右遍历。
当出现重叠区间的时候，更新重叠区间的右边界为当前区间的右边界就可以了。这样就达到了更新重叠区间的效果。
如果没有出现重叠，那么就应该把当前区间作为一个新的重叠区间压入结果数组。
其他难题
最大子序和
从优化暴力解法的思路出发，贪心解法的本质是优化了暴力解法的外层循环，即起始位置循环的判断。
核心思想：
以当前的子序和为视角，每次选择时都可能让子序和更大：
当子序和负数时，替换新子序和，因为无论如何加下一个数都不如直接选下一个数成为新子序和大
当子序和正数时，直接加新数字，因为无论如何替换下一个数都不如当前子序和加数字大
加油站
暴力解法的思路是从头到尾以不同站点作为起点，两个循环验证是否可行的起点。
那么，外层使用for循环，内层使用 while 循环。
每个加油站都有剩余油量，然后累加剩余油量。如果累计剩余油量小于0，那么就说明之前的位置都不能算作起始位置。起始位置就要从i+1算起。
这里贪心贪的是，一旦剩余油量小于0，就没有一一确认之前的位置是否能做起始位置。而是贪心地认为之前的位置都不能算作起始的位置。这个过程也就时优化了暴力解法的外层循环。
这样不断的排除，找到了能够作为起始位置的位置。
最后，用一个总油量减去总消耗量大于等于零的条件判断。如果总剩余油量大于零，那么最后一个没有排除的位置就是实际位置，因为题目告诉我们存在唯一解。
如果总剩余油量小于0，那么就不存在解。
监控二叉树
为了让摄像头安装的最少，应该使得总的覆盖范围最大。因此，让叶子节点安装摄像头就是吃亏的。因此，让叶子节点的父节点安装摄像头，这样就节省掉了很多摄像头。
顺序是后序遍历，因为摄像头安装与否取决于其孩子有没有被覆盖。
每个节点有三个状态，分别是无覆盖、有摄像头、无摄像头但被覆盖。
最后，额外考虑跟节点没有被覆盖时的特殊情况。