贪心题目难与易，一念之间，看出来就是看出来了，看不出来也很难自己想出来。没有鲜明的题目特色，需要通过刷题和总结题型提高自己的能力。
==左边界排序 or 右边界排序？==
==这与遍历顺序有什么关系？==
大胆推测：任何题目都能够用两种排序方式做，只不过需要在遍历顺序或者取活动端点的最大最小值方面做一些调整，
给定一个区间的集合，找到需要移除的区间的最小数量，使剩余区间互不重叠（某个点的重合不算重合）。
给定一组气球占据的x轴的范围，求射爆所有气球至少需要几枪。
此题有4种解法，分别对应左排序+正叙，右排序+正叙，左排序+倒叙，右排序+倒叙
给定一个只由小写字母组成的字符串s，我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回划分的长度序列。
输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
分析：本题与前两道题的最大不同是是按照a[0]大小排列。
给定一组区间intervals，将重叠的区间进行合并并返回。
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
合并区间：希望非活动端点侧按序排列
左正右倒+更新活动端点最大值
无重叠区间：希望活动端点一侧尽可能的小
右正左倒+活动端点值固定为第一个区间的end
射气球：在遍历中更新活动端点最小值，如何排序和遍历无所谓
有一部分股票交易问题实际上可以用贪心法来做。
只交易一次
交易次数不限
每交易一次，多支付一笔手续费
现有一群孩子排成一列，数组ratings代表每个孩子的评分。现在老师要给孩子们分发糖果，规则如下：
- 每个孩子至少得到一块糖果
- 相邻的孩子中评分更高的将得到更多的糖果
求老师最少需要发多少个糖果？
分析：题目从两个维度对任意位置的孩子得到的糖果数进行限制。如果比他左侧的评分高，则得到更多的糖果；如果比他右侧的评分高，也得到更多的糖果。
现有打乱顺序的一群人站成一队，每个人用一个数组表示[h,k]，其中h表示这个的高度，k表示在原本正确的序列中这个人前面有多少个比他高的人。要求你重建其正确的排队序列。
输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。
反思
自己当时想的是身高从低到高排序，实际上身高从高到低排序更加的方便，代码更加的简洁。
一杯柠檬水5块钱，顾客使用三种面额之一的零钱付款：5元，10元和20元，给定一个顾客数组，数组代表其持有的零钱面额。刚开始你没有一分钱，问在给定的顾客序列下你能否对每一个顾客正确找零？
输入：[5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。
分析
我们发现当顾客付5元时不需要任何的找零，而付10元和20元时分别需要找零5元和15元。
进一步的思考发现，5元比10元更为“珍贵”，因为5元可以用来找任何零钱，而10元只能用于找20元的零钱。
因此我们制定了策略，当给20元的顾客找零时，优先花10+5元的组合，而不是花3张5元，这样可以尽可能地保留更多的5元。
反思
这道题的贪心策略还是比较容易看出来的。**但是在代码的具体实现中自己还是浪费了很多的空间。**使用了一个map保存每张面额的纸币的数量。其实这根本没有必要，用一个数组甚至两个变量都能完成这个任务。
==思考：贪心算法和动态规划的总体思路区别在哪？====
==什么样的题目适合使用贪心算法，什么样的题目适合用动态规划解决？==
给定一个数组，你现在在第一个位置，数组每个元素代表你在这个位置可以跳的最远距离。判断给定数组能否让你到达最后一个格子。
分析
自己最想想到的是动态规划，具体思路如下：
- 设定$dp[i]$的含义为：该格子能否被到达true/false
- 对于每个i，遍历其$[0,i-1]$，$dp[j]==true$且$nums[j]+j>=i$，则$dp[i]=true$
总体时间复杂度为$O(N^2)$
其实这道题可以用贪心的思路，我们需要明确这样一件事情。对于格子i，如果它能够被跳到，那么i之前的格子也必然会被跳到。实际上，我们只需要维护一个最远跳跃点即可。
贪心：维护一个最远距离dist,i在dist内遍历，当$dist>=nums.size()-1$时，证明能够被跳到。如果遍历完dist还不满足条件，则说明跳不到最后一个格子。
题目条件如上，但现在的问题是求跳到最后一个格子最少需要多少步？可以假设最后一个格子总能够被跳到。
分析
承接上一题的思路，我们可以维护一个curDist和一个nextDist，i在curDist内移动，不断更新最远距离nextDist。当遍历到curDist时，步数step++，且令curDist = nextDist，同时我们需要判断若$curDist>=nums.size()-1$，结束所有循环，返回当前步数step
给定一个数字，求不大于该数字的最大单调递增数字。
当且仅当每个相邻位数上的数字x和y满足x<=y时，我们称这个整数是单调递增的。
输入: N = 332
输出: 299
输入: N = 1234
输出: 1234反思
基本思路想的是八九不离十，编译写的代码也通过了。但是离最优答案还是有差距。
我的思路：
-
将给定的数字转换为
string，从前向后遍历，当遇到numStr[i]<numStr[i-1]时，开始循环。 -
首先将numStr[i-1]--；判断numStr[i-1]>=numStr[i-2] && i>1
-
若符合条件，从i开始到结尾全部置为‘9’
-
若不符合条件，令i=i-1，回到循环入口。
- return stoi(numStr)
时间复杂度为$O(N)$
参考答案的思路：
- 前面不变，但是从后向前遍历。
- 维护一个变量
flag，表示置9的起点。遍历过程中遇到numStr[i]<numStr[i-1]，将flag置为i - 遍历结束后，从flag到结尾全部置'9'（注意flag初始值设为numStr.size()）
- return stoi(numStr)
时间复杂度也为$O(N)$ 但是代码非常的简洁。
遍历顺序的重要性！
给定一个数组，里面有若干数字。同时给定一个数字k，代表翻转次数。每翻转一次，都将数组中的某一个元素取负值。求k次翻转后这个数组的最大数组和。
反思
自己思路出的还是比较快的。但是空间复杂度还是高了。
自己一开始的思路：维护一个priority_queue，小顶堆，每次都将顶部元素取反后重新加入到队列中。这样总体的时间复杂度为$O(2klogN+logN)$ ，因为每一次操作相当于删除一个元素又插入一个元素。空间复杂度为$O(logN)$
但是参考答案的思路并没有使用priority_queue，而是使用了两次贪心策略。
- 首先按照绝对值从大到小进行排序$O(logN)$
- 从前向后遍历数组，对小于0的数组进行翻转。$O(logN)$
- 若遍历到尾k仍大于零，则无限地翻转数组最后一个元素$O(k)$
- 数组求和$O(logN)$
总体时间复杂度为$O(3logN+k)$，比我的方法稍高一点。但是空间复杂度为$O(1)$
给我的教训是，每次使用空间时，想想是否真的有必要，有没有办法不使用就解决问题！
两数之和
假设答案只有一个 且必然存在答案
回溯：答案有很多个 回溯等同于暴力O（n2）还需要加上递归调用耗费的栈空间