经过贪心算法的洗礼，个人对贪心算法也有了一些粗浅的认识。
首先，什么是贪心算法？
贪心算法的本质就是取阶段性局部最优的情况，再综合每一阶段达到全局最优。这么说可能有点抽象，举个例子吧，假如说有一堆大小不同的金币，限时不限量的让你拿走，那肯定要从最大的金币开始挑，按 最大->次大->中等->小 这样的顺序，包你赚的最多。每次选最大的金币，实际上就是取阶段性的局部最优。
其实在写算法题的时候，个人感觉贪心是很抽象的。这种抽象分为几个方面，一是无法直接确定题目使用贪心算法求解，二是贪心算法没有固定的套路和模板，三是贪心算法太依赖常识性或灵光一现的想法。
没有其他办法，只能多做多总结，下面根据《代码随想录》，按难易度对题目进行归类总结。
贪心简单题
这三道题目均是简单难度，根据常识来进行解题即可，但是要分析题目中的局部最优。
贪心中等题
从中等题开始，只靠常识解题是不够的，必须要找到局部最优的情况才行。
- 376. 摆动序列 ⭐ 这道题初见二见都未ac，需细细品味
- 738.单调递增的数字
摆动序列的难点是，只需把序列元素值看作高峰低峰进行画图，我们只收集摆动的序列元素，对于平坡或递增/递减情况，只记录前一个坡段的插值进行不断比较即可。
单调递增的数字的难点是，我们要从后向前遍历，出现strNum[i – 1] > strNum[i]的情况（非单调递增），首先想让strNum[i – 1]–，然后strNum[i]给为9。但是要考虑到类似于 100 这种数的情况，要记录变为9的起始位置，在最后遍历一次数组，将应该变成9的数位变为9。
贪心解决股票问题
股票问题其实是动态规划的专长，但是贪心算法也可以解决一些。
这道题的难点是，要想到每天的利润是可以分解的，例如第 0 天买入，第 3 天卖出，那么利润为：prices[3] – prices[0]。
相当于(prices[3] – prices[2]) + (prices[2] – prices[1]) + (prices[1] – prices[0])，能想到这一步，这道题迎刃而解。
两个维度权衡问题
在出现两个维度相互影响的情况时，两边一起考虑一定会顾此失彼，要先确定一个维度，再确定另一个一个维度。
这两道题的思路非常相似，都是在两个维度上进行排序的思路，那我们就要先确定一个维度（比如从左到右还是从右到左，升序还是降序），再去确定另一个维度就好办了。另外，406这道题还可以锻炼LinkedList的理解和使用。
贪心难题
贪心的难题，即便不是hard也是胜似hard，非常难想到。就算初见，二见三见也很难ac，所以这里的题目要多练（菜就多练.jpg）。
贪心解决区间问题
跳跃游戏的破局在，并不需要去思考跳几步，只需要记录可跳的最大覆盖范围。
跳跃游戏II异曲同工，但要难不少。除了记录可跳的最大覆盖范围curCover外，要思考什么时候跳数加一，这就需要记录上一次的最大覆盖范围preCover，当我们走到preCover时，就需要更新curCover并判断是否已经可以达到最后一个元素位置。
用最少数量的箭引爆气球，很容易想到按左边界升序排序，难点在于判断重叠时，如果不重叠，我们应该更新边界以防下一个区间也和现在判断的两个区间重合。
无重叠区间，和上一题大同小异，同样也需要更新边界。
划分字母区间，只要想到记录字符串中每个字母最后出现的位置，再根据每一步去判断即可。
合并区间，和无重叠区间很像，但是要想到，直接在集合处理合并即可，不需要在数组层面合并。
其他难题
最大子序和，其实是更易于想到动态规划求解的，但是也可以使用贪心。
加油站，这道题更像是模拟过程，难点在于想到如果每天相减后的剩余油量全部求和，为负数时是不可能有解的。
单独给监控二叉树这道题一个排面，仅贪心的思路不好想，而且需要对二叉树的操作特别娴熟，这就是典型的交叉类难题。我是真想不出来做法，这种题就只能多做多记，做的多了举一反三了。
