所有代码详见：https://github.com/jingminglake/Leetcode
总体思路
贪心的题目往往比较难，因为很难证明贪心策略是正确的。
至于贪心的解法，一般是求最优解，此时要做的不是暴力看所有的情况，而是以某个接近答案的值作为初始值，然后经过贪心的变形， 就可以变成最后的解。
具体题目
738. Monotone Increasing Digits
题意：求比一个自然数小且单调递增的数中最大的那个。例如对于1002来说，答案是999.对于14436来说答案是13399。
解：寻找要求解答案的规律，发现，答案是原来的数从右向左看，第一个比自己右边大（违反递减）的数字可以减1，然后后面全部用9补齐。
注意相等的边界条件：
(1) 例如1455中第一个5违反递减规律，但是第一个5减1后，之前的4也会违反规律。因为1455的答案是1399，真正违反规律的是4。
(2) 例如17756，那么违反规律的是第一个7，而前7变为6后，前面的第一个7也会违反规律。
这里要做的就是只要出现违反，那么就立即就地减1，继续往前扫描。
452. Minimum Number of Arrows to Burst Balloons
题意：给出区间数组。把区间当作是气球，然后，区间点上射箭会让气球爆炸，现在求让全部气球爆炸的最小射箭次数。
解：先按照区间的右端点的由小到大排序。然后，从第一个右端点开始射箭，看一次能射爆几个气球（只要后面区间的左端点小于射箭点就可以被射爆）。
对排序好的区间一遍扫描，每次更新最近射箭点，更新的方法就是跳过可以被射爆的区间，然后每次更新射箭点，需要的箭的数量就加1。
605. Can Place Flowers
题意：给出0和1的数组，1代表花，现在要向数组里面加入花，要求是花和花之间必须要有间隔。
解：贪心法。从头到尾扫描一遍数组，如果能放入花，那么就放。
621. Task Scheduler
题意：给出字母数组，字母代表一种任务，每种任务单位时间为1就能解决，在给出一个CPU间隔n，表示不同任务执行之间必须要有n个单位时间的间隔。例如：A任务执行后，必须要执行n-1个其他任务，然后才能重新执行A，如果没有那么多种类的任务，那只有空闲着单位时间了。要求解的是执行完所有任务花费的最少时间，任务执行顺序不受数组顺序限制。
解：此题是贪心的，通用解法就是，把任务装进优先级队列，然后每次往每一轮里面装。
由于每个任务都是间隔时间为n，那么假设n足够大（比任务种类多），那么会发现执行完所有任务其实取决于数量最多的任务，只要每一轮间隔优先执行数量最多的任务，期间安插一些其他任务，就是最优解的形式。
当n比任务种类小的时候，贪心的放入，由于每一轮都将被放满，所以最后的长度就是等于任务的数量。
有了最优形式解，那么如果编写程序模拟这样往里面填，其实还是有操作难度的，所以最好还是进一步找答案的规律。当n很大的时候，最优解的形式，假设数量最多的任务数量是maxN，那么前maxN-1轮是不会一定有的，也就是前maxN-1轮的结果一定是(maxN-1)*(n+1)。再来考虑最后一轮，由于前面已经间隔插入了其他任务，所以留到最后一层的任务必然是等于数量最多的任务的（任务数量最多的可能不止一个）。只要加上即可，当然有一种例外，那就是发现最后一轮的任务超过了间隔数，或者算出来的任务比任务的个数（下限）还要少，那就就选任务的个数做结果返回。
PS.计算数量最多任务种类时候，要从map遍历，不能从原数组进行遍历。另外，在max中使用size()时候，要显式转化为int。
253. Meeting Rooms II
题意：给出开会开始结束时间区间为元素的数组，开会房间不能重叠，求开会所需要的最少房间数量。
解：此题使用贪心法。原理是这样的：先按会议开始时间将所有区间进行排序，然后扫描每个区间，模拟分配房间的过程：
首先，第一个区间占一个房间；对于第二个区间，如果第二个区间的开始时间大于第一个区间的结束时间，意味着第二个区间可以使用第一个区间分配的房间，反之，则要新开一个房间给第二个会议使用。 对于第三个房间，如果前面分配的是一个房间，那么要看第二个会议结束时间和自己的开始时间；如果前面分配的是两个房间，那么，看自己起始时间是否比其中的一个结束时间要小，要是比两个都小，那么就只能新开第三个房间，否则就占用其中一个最早结束（所以是贪心法）的房间。
接下来的问题是，如何从正在开会的几个房间中选出最早结束的房间，使用的方法就是heap。所以说，这个问题是一个sweepline解法。
484. Find Permutation
题意：给出n-1大小的串，由D和I组成，第i位为D代表第i位到第i+1位是递增的，第i位为I代表第i位到第i+1位是递减的。求1，2，…，n的排列中满足条件最小的那个。
解：求全排列然后验证时间复杂度太高，而题目中包含最这个关键字，因此考虑使用贪心。
方法就是一开始初始化为123..n，看相应位置是不是违反了对应的D和I的规律，如果反了，那么就翻转，其实就是看D出现的位置，把D出现的位置全部连续的做翻转就可以了。
316. Remove Duplicate Letters
题意：”cbacdcbc”变为”acdb”。意味着，删除全部重复字母直到每个字母剩余一个，我们从中间选取字典序的作为结果，也就是说从cbad, cdbc, acdb, bacd中选取acdb作为结果。
解：此题解法是贪心。此题类似于区间问题来分析，每个字符作用范围是一个区间，那么先结束的区间总是优先级最大，需要尽量排在最前面，例如cbacdb，其中的最先结束的区间是a，对于a之前的字符c和b，由于可以在后面又重新出现，所以完全可以删掉，只保留后面bc。
这里a的字符优先级本来就高，先看一个例子bacba，这个例子里面，c是最先结束的区间，但是还是要保留前面的ab，因为ab的字符优先级比c高，那么答案是bac吗？不是，最终答案是acb。
所以此题字母的作用范围不是开头结尾的区间，而是字母出现的每个位置点。
类似的题目就是删除数字得出最大数字的402题，只要把402题的删数字个数变成删除重复数字就得到这一题。
此题解法就是使用单调栈+hash。从左到右扫描整个字符串，单调栈一直维持一个升序的，也就是最小单词序的序列，一旦发现更小的字母时候，我们看栈顶元素是不是在后面还存在，如果存在，那么删除掉，否则保留。
还要注意的是，看当前字母是不是已经存在在栈里面了，如果已经存在，那么对该字母不需要任何操作。
具体做法是：首先计算每个元素出现次数，然后扫描整个字符串，遇到元素的时候，先把元素个数减1，然后看元素是不是已经访问过了，如果访问过了就跳过此元素的处理，如果未访问过，那么将该元素与栈顶相比，如果栈顶元素的ascii码大于当前扫描元素，且栈顶元素的个数大于0(表示后面还会出现栈顶元素)，那么弹出栈顶元素，并将栈顶元素标记为未访问；如果比栈顶元素大，那么暂时先入栈且暂时标记为已访问，说明栈中所有元素暂时都是合法的。
使用单调栈的原因是贪心，贪心的让每一种元素尽可能的出现的更早，直到发现一个元素使得之前元素不合法，这个时候，我们才去尝试修改之前的选择。
418. Sentence Screen Fitting
题意：给出行列数量以及单词数组，求填充行列的情况下，需要使用多少个数组。
解：此题一开始是以为模拟对每行每列进行填充就可以了，但是这样时间复杂度高。进一步观察知道对于每一行，必然会以某个单词开头进行填充，而绝不会出现以空格开头的情况，所以，在行比较多的情况下会存在大量的重复，就以题目中的rows = 2, cols = 8, sentence = [“hello”, “world”] 来看，如果每次都是模拟往每行里面填单词，每次填单词消耗cols的时间，那在rows很大的情况下，就是消耗rows * cols的时间，但是我们知道，只存在两种模式，就是hello__和world__。
所以，此题可以使用动态规划记忆化方式来减少出现重复时候的计算时间。
使用一个hashmap<int, int>来保存从数组中第i个单词开头，此行能放下多少个单词，扫描完全部行之后，总的能放下的单词数除以数组大小向下取整就是单词数组的数量。
另外一种解法是先把单词数组连起来，然后放入行进行匹配，这种解法相比于一个一个单词放入解法的好处是贪心，由于列比单词长度大的多，所以匹配策略就是尽可能的先多放单词，实在发现不行就进行回退：减一个看看，不行再继续减…
774. Minimize Max Distance to Gas Station
题意：给出加油站数组，数组里面的数字表示加油站在x轴上的坐标，现在又给出k表示可以新插入k个加油站，现在求插入后使得加油站间最大距离可以减少到多少。
解：先理论上解题，然后再看有什么具体方法解题。此题n-1个区间，然后要加入k个分割点，我们知道，一个分割点只能是处于某一个区间，而要达到最佳效果，那么分隔点必须要平分一个区间，例如一个区间内含有3个分割点，那么最佳策略就是三等分这个区间。
那现在就有一个贪心策略了，每次选择区间长度除以区间现有的分割点的结果中最大的那个区间，插入一个新的结点。为了保证每次选最大的，可以使用优先级队列。时间复杂度为O(k * logn)，空间复杂度为O(n)。可惜的是这种方法超时了，这种方法缺陷就是如果k太大，时间总是依赖k。
另一种方法就是使用二分法，使用二分法之后，发现可以屏蔽掉k对时间复杂度的影响。二分法的对象是区间的最大段长度x，x一开始是介于0到无穷（题目要求），但是对于每个最大段长度x，我们可以在O(N)的时间内验证其合不合法，方法就是把每个区间都按照最大长度切分，看能切成几块，切了之后加起来的数如果小于等于K，那么就合法，否则不合法。
理解：一开始从0到n之间有n-1个区间，现在通过多放入k个点分割多出来k个区间，所以我们知道这些点要切分其中的大区间来使得最后所有区间是更加均匀的。
其中要通过加入点来切割的那些区间（原来长度大于最大段长度的区间），最终内部每段的长度都是小于或者等于最大段长度的，而其他所有不加入点的区间，他们的长度本身就是小于等于最大段长度的，所以不引入新区间。结论就是：第一类通过加点来切割的区间除以最大段长度得出来的区间个数，加起来只会小于等于K。换句话说，就是新引入的K个区间最好每个的大小都和最大段长度x一样，如果其中有些达不到最大段，即其中蕴含的最大段数量不足，那么说明这个大小是合法的，也同时说明最大段长度可以进一步减小来优化；如果按最大段来切，切出来的区间数居然比K多，那么说明最大段太小，不合法。
358. Rearrange String k Distance Apart
题意：给出一个串和整数k，要求是重新安排串，使得相同字符之间间隔至少是k。返回重新安排的串，如果不存在就返回空。
解：此题使用贪心法，先放置字符个数最多的字符，再放置次多的字符。如果剩余的字母种类数比下一轮要放的空格数小，那么直接返回空，每一轮要放的空格数是k和剩余串长度len中的较小值，每放一轮后，该轮放入的字母的个数减1，然后进行下一轮。
仔细想来，题意是要求两个相同字符之间有间隔k，所以严格意义上来说，每一轮都要放入k个特殊字符，如果k大于当前剩余字符串长度，那么在之前的操作中k轮放入k个不同字符，可以完美的保证两个字符相隔k；如果k小于当前剩余字符串长度，那么说明此轮只能放入剩余字符串的长度的字符，而且只能是最后一轮。无论是哪一轮，都必须遵守放入特殊字符的条件，一旦不符合，马上就返回空。
此题使用的数据结构就是优先级队列，每次选择堆顶字符，然后弹出来表示此轮不能再选了，如果当前字母对应的次数仍然不为0，那么就加入一个临时数组保存下来，然后下轮之前将临时数组中的信息重新添加到优先级队列中去。
55. Jump Game
题意：整数数组里面数字代表可以跳到多少数字之后，从第一个数字出发，问能不能跳到最后一个数字。
解：只要遍历一遍数组就可以，每次走一步，并更新当前能走的最远位置，如果当前走的位置比当前能走的最远位置小且比最后一个位置小，那么就继续走，否则退出，然后比较当前位置是不是在最后一个位置上。也就是说一步步走一定能走到最后一个位置。
135. Candy
题意：数组代表小孩分数，现在要求分糖果，要求不能比左右人领的糖果少，这样发的最少总糖果数，每个人至少一个。
解：贪心法，扫描两遍，第一遍从左到右，满足小孩不比左边分低的拿得少，然后第二遍从右到左，保证不破坏之前性质的前提下，保证不比右边分低的拿得少。
