关于贪心学习的文笔记录

贪心，顾名思义就是越贪越好，越多越有易，他给我的感觉是，通常是求最大或最小问题，相比于动态规划贪心让人更加琢磨不透，不易看出方法，为此在这记录我所见过的题型和思维方法，以便回头看看…

核心思想:动态规划是借用之前所有的最佳状态，来推理出当前的最佳状态，与众不同，贪心则是不需要之前的状态，根据一个价值标准’拿的越多越好’,然而这种价值标准必定没有影响后效性，比如来到某个状态点时，消耗了较高代价拿到了最大效益，虽然对于当前状态来说，但是对于未来的某个·点来说，也许有更加好的选择消耗更少的代价来获取较高的效益，所以通常贪心的目的是，找到一种标准价值，按照标准价值来越多越好，或者是通过一定单调性排序，确保每一步都是最优解，然而这一步通常是最难的。

632. 最小区间

你有 k 个 非递减排列 的整数列表。找到一个 最小 区间，使得 k 个列表中的每个列表至少有一个数包含在其中。
我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。

示例 1：
输入：nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
输出：[20,24]
解释：
列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。

这是一道困难题，确实不好想,他的解题思路是，一直观察每个数组的最小值，对于这几个值来说，当前几个数的值显然是最小的那个数的最佳状态，不好解释为什么，凭想吧。于是可以将这个数的价值记录并弹出，依次循环，再找出最佳结果。

135.分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的最少糖果数目 。

记得第一次作这题时，确实被这种思维感到震惊，后来发现这种思维其他题也会用到，因此是一个不错的例题。

尽量少的分发糖果，我们先将每个人分发一个糖果，正向遍历，如果后一个人的分数大于前一个人，那么后者在前者的基础上加1(确保右边人分数大时，右边人的糖果合理大于左边)，再次逆向遍历，左边大于右边人分数时，左边人糖果为右边人糖果加1（确保左边人糖果的合理性);

这种两次遍历的思维，将在下一题同样遇到。
581. 最短无序连续子数组

给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
请你找出符合题意的 最短 子数组，并输出它的长度。

这题同样是利用左右两次遍历，有上一题的思维。

要想找到不合理的区间，我们只需要找到最右边的不合理数，以及最左边不合理的数，那么什么叫做不和理呢？显然是左边的数大于右边或者右边的数大于左边的数，如果一个数的左边没有比他大的数，右边同样没有比他小的数，那么说明该数是一个合理的数，我们可以先正向遍历，筛选出左边比自己大的不合理的数，然后再逆向遍历筛选出右边小于自己的数，挑出最左边和最右边下标就可以了。

这题与上一题唯一不一样的是，上一题是构造合理环境，这一题是检查不合理环境。

根据规律判断贪心

分成K份的最大乘积

问题：一个数字n一定分成k份，得到的乘积尽量大是多少，数字n和k可能很大，结果需对100000007取模。

这题第一眼想到的是暴力递归，但是即使是记忆化搜索，对于较大数字，也难免会超时，我们先尝试前几个数字最大解，观察一下结果
n=4 2 * 2
n=5 3 * 2
n=6 3 * 3
n=7 2 * 2
n=8 3 * 3 * 2
n=9 3 * 3 * 3
n=10 3 * 3 * 2 * 2
n=11 3 * 3 *3 * 2
n=12 3 * 3 * 3 * 3
n=13 3 * 3 * 3 * 2 * 2

可以发现，当一个数大于4时，可以拆出3时尽量拆3，这样使得乘积最大，当然可以用数学极限来证明，但是还是当作例题记录一下的好。在遇到类似的题也可以考虑一下找规律，虽然这样的题很少，但是对于没有思路的数学问题，还是可以使用这样方法快速找到规律来解题的

排序使问题呈现一定单调性

执行所有任务的最少初始电量
每个任务有两个参数，需要耗费的电量、至少多少电量才开始这个任务
返回手机需要的初始电量，才能执行完所有的任务

仔细想想，我们不难发现，当需要消耗的电量相同时，那么我们应该先让至少电量最多的任务先完成，当至少电量相同时，应该让消耗电量少的先完成。
但是问题来了，如果需要消耗少的与至少电量少组合在一起，或是消耗多和至少多的组合在一起，那么我们应该怎么判定优先级呢。既然这样的话，我们将至少电量减需要电量作为值，来排序优先级，直观上感觉是对的，事实上也确实如此，但是关于证明我还没有想好，有点玄学。
对于有的题，此法是行不通的，我见过类似的题目，但是将两因素作差值为优先级并不适用于所有题

知识竞赛
最近部门要选两个员工去参加一个需要合作的知识竞赛，每个员工均有一个推理能力值 ai,以及一个阅读能力bi，如果选择第i个人和第j个人去参加竞赛，两人在推理能力方面的能力为其两者推理能力的平均值，阅读能力同理，现在需要最大化他们表现较差一方面的能力，问这个能力值是多少。

这题依旧是排序解决，只不过是按照两元素差值的绝对值来排序，依次遍历每一个人，寻找前面的人与这第i号人的组合最大值，排序后巧妙之处在于，每当来到第i号人，都可以快速求出，第i号人与前面的人组合的最有解，那是因为，对于第i号人来说，他与前面任意一个人组合必定是自己能力最小的作为结果，由于绝对值排序的缘故，前面任何一个人都不可能弥补第i号人在弱势能力上的差距，所以我们只需要记录前面所经过的两能力各最大值即可，每次来到第i号人都可以快速求出组合最优解。
从这题我们应该学到的是，当不得不暴力求解时，尝试寻找一种策略，使得快速找到一种结果对于第i元素来说一定确保其为最优

可以掌控全局变量的最优决策

在01背包里，其关键思想就是要或者不要,来到某个状态时，可以根据前面的所有最佳状态获取当前的最佳状态，当然，这种思维并不只是在动态规划里可以使用。
871. 最低加油次数

汽车从起点出发驶向目的地，该目的地位于出发位置东面 target 英里处。
沿途有加油站，用数组 stations 表示。其中 stations[i] = [positioni, fueli] 表示第 i 个加油站位于出发位置东面 positioni 英里处，并且有 fueli 升汽油。
假设汽车油箱的容量是无限的，其中最初有 startFuel 升燃料。它每行驶 1 英里就会用掉 1 升汽油。当汽车到达加油站时，它可能停下来加油，将所有汽油从加油站转移到汽车中
为了到达目的地，汽车所必要的最低加油次数是多少？如果无法到达目的地，则返回 -1 。
注意：如果汽车到达加油站时剩余燃料为 0，它仍然可以在那里加油。如果汽车到达目的地时剩余燃料为 0，仍然认为它已经到达目的地。

这题，可以使用动态规划思想解决，那么我们要维护的信息是什么呢，当油不够时，我们更期望之前在存储油最多的加油站加油，于是需要维护路过的加油站，对于来到第i个地点来说其最佳状态为以下两种情况 第一：油不够时dp[i]=之前最大加油站的油+当前剩余的油-当前消耗的油，第二：油够时，dp[i]=dp[i]-当前消耗的油；唯一贪心的点在于选取之前路过的最高存储油量的加油站。