贪心介绍 LeetCode 455.分发饼干 LeetCode 376. 摆动序列 LeetCode 53. 最大子序和

贪心介绍

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

eg: 有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿？

指定每次拿最大的，最终结果就是拿走最大数额的钱。每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。

但这种实现方式不一定总能达到全局最优。如有一堆盒子，你有一个背包体积为n，如何把背包尽可能装满，如果还每次选最大的盒子，就不行了。这时候就需要动态规划。

注意点：

• 贪心有什么固定的套路实现吗？说实话贪心算法并没有固定的套路。
• 那么如何能看出局部最优是否能推出整体最优呢？有没有什么固定策略或者套路呢？不好意思，也没有！ 靠自己手动模拟，如果模拟可行，就可以试一试贪心策略，如果不可行，可能需要动态规划。
• 如何验证可不可以用贪心算法呢？最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。

贪心算法一般分为如下四步：

• 将问题分解为若干个子问题
• 找出适合的贪心策略
• 求解每一个子问题的最优解
• 将局部最优解堆叠成全局最优解

做题的时候，只要想清楚 局部最优 是什么，如果推导出全局最优，其实就够了。

LeetCode 455.分发饼干

思路

• 将孩子的胃口和饼干的大小进行升序排序，通过两个指针来控制当前使用的饼干和当前吃饼干的孩子。
• 如果当前饼干大于孩子胃口，则两个指针都右移。如果当前饼干小于孩子胃口，则饼干的指针右移，去获得更大的饼干。
• 总的思路就是拿小饼干去喂给小胃口的学生，针对需要大胃口的学生才给大的饼干。

手撕Code

class Solution(object):def findContentChildren(self, g, s):""":type g: List[int]:type s: List[int]:rtype: int"""### g[]是孩子；  s[]是饼干### 思路：对孩子的胃口和饼干的大小的升序排序，在两个数组中通过两个指针来判断当前饼干大小能否符合孩子的胃口。g_sorted = sorted(g)s_sorted = sorted(s)g_left = 0s_right = 0num = 0# print("g_sorted, s_sorted", g_sorted[g_left], s_sorted[s_right])while True: if s_right == len(s_sorted) or g_left == len(g_sorted):breakif s_sorted[s_right] >= g_sorted[g_left]:  ## 当前饼干的大小 比当前孩子的胃口大num += 1s_right += 1g_left += 1elif s_sorted[s_right] < g_sorted[g_left]:                 ## 饼干的大小 不足以满足当前孩子的胃口s_right += 1return num

Code

class Solution:def findContentChildren(self, g, s):g.sort()  # 将孩子的贪心因子排序s.sort()  # 将饼干的尺寸排序index = 0for i in range(len(s)):  # 遍历饼干if index < len(g) and g[index] <= s[i]:  # 如果当前孩子的贪心因子小于等于当前饼干尺寸index += 1  # 满足一个孩子，指向下一个孩子return index  # 返回满足的孩子数目

又或者通过一个for循环来遍历饼干，如果饼干大小大于孩子的胃口时，再修改指向的孩子。

LeetCode 376. 摆动序列

需要考虑三种情况

1. 上下坡有平坡
2. 首尾元素
3. 单调坡有平坡

需要明确判断当前节点是否满足摆动序列，如果当前节点的两边没梯度变化或者两边的梯度变化都是同向的，那就证明这个节点不符合摆动序列。这道题的贪心算法就是像不考虑这些，只考虑那些局部顶点或谷点。需要加以折现图辅助理解。

思路：

• 通过一个prediff来记录当前节点与上一个节点的坡度，一个curdiff来记录下一个节点与当前节点的坡度。①如果prediff和curdiff为异号，那就证明当前的这三个节点符合摆动序列。②如果prediff和curdiff中其中一个为0，另外一个不为0，那就证明这三个节点中有两个节点符合摆动序列。③第②种方法存在缺陷，即整个序列是单调坡有坡的时候，此时，基于②去计算摆动序列长度的话会多算了。如何优化？当curdiff与prediff异号时，我们此时再更新prediff的位置。
• 序列是从左到右进行遍历的，我们要从第二个元素开始进行遍历，先计算prediff和curdiff，当移动到下一个元素时，此时，先计算curdiff的值，如果curdiff与prediff异号，则将curdiff赋值作为prediff即可，之后再继续进行遍历。
• 对于序列的第一个元素，其是没有prediff的，那么将其prediff看成是0，即其prediff是自己减掉自己。通过判断后续的curdiff来判断第一个元素是否符合摆动序列。
• 根据以上curdiff和prediff所对应的出现摆动序列的情况进行计数。

左右梯度不同的情况

左右梯度存在一方为0的情况（非单调坡存在平坡）

左右梯度存在一方为0的情况（单调坡存在平坡）

手撕Code

class Solution(object):def wiggleMaxLength(self, nums):""":type nums: List[int]:rtype: int"""if len(nums) == 1:return 1result = 0for i in range(0,len(nums)-1):if i == 0:prediff = nums[i] - nums[i]       ##只需计算一次，后续通过curdiff去更新prediff就行curdiff = nums[i+1] - nums[i]if (prediff >= 0 and curdiff < 0) or (prediff <= 0 and curdiff > 0):result += 1         ### 当前的这个节点是符合摆动序列中的局部最高/最低，而不是在单调坡的坡上prediff = curdiffreturn result+1

以序列nums = [1,7,4,9,2,5]举例，其流程如下：

LeetCode 53. 最大子序和

思路：

• 采用连续和 + 下一个元素值的局部搜索方法去进行判断。当连续和为负数的时候，这时候就需要丢弃之前的计算了，因为你拿这个负数的连续和去进行相加只会是负担（让你去获得和最大的工程中）。因此当连续和为负数时，将count归零，从下一个元素开始进行计算。
• 第一种方法适合于数组中存在正数和负数的情况，那对于全为负数的情况的话要另外解决。相对比较简单，对数组进行排序，如果数组的最大值为负数，那这个数组的最大值元素的值就当前这个全为负数的数组的最大子序和。

手撕Code

class Solution(object):def maxSubArray(self, nums):""":type nums: List[int]:rtype: int"""### 不能对原数组进行排序来判断，这样的话你手动修改了数组的顺序。输出的数组在原数组不一定连续### 思路 ： 连续和 + nums[i]， 当连续和是负数的时候，此时就抛弃掉前面的元素，从下一个元素开始进行计算###                            另外，当连续和大于目前result的话，则将result进行更新，证明你补充下个元素进去有利于和变大result = 0count = 0path = []for i in range(len(nums)):      ### 针对数组中存在正数和负数的情况count += nums[i]if count > result:result = countif count < 0:count = 0nums_sorted = sorted(nums)             ### 如果整个数组都为负数, 那直接取负数中最大的一个值if nums_sorted[len(nums)-1] < 0:return nums_sorted[len(nums)-1]return result