算法训练营第二十三天 | 贪心算法（一）

文章目录

一、贪心算法理论基础
二、Leetcode 455.分发饼干
二、Leetcode 376. 摆动序列
三、Leetcode 53. 最大子序和

一、贪心算法理论基础

贪心算法是一种在每一步选择中都采取当前状态下的最优决策，从而希望最终达到全局最优解的算法设计技术。

基本思想

贪心算法总是做出在当前看来是最优的选择，也就是说，它不从整体最优上加以考虑，所做出的仅仅是在某种意义上的局部最优解。它通常以自顶向下的方式进行，每一步都选择一个局部最优解，逐步构造出问题的解。

使用条件

贪心选择性质：问题的整体最优解可以通过一系列局部最优的选择来达到。即每一步的最优选择最终能导致全局的最优解。
最优子结构性质：问题的最优解包含了子问题的最优解。也就是说，原问题的最优解可以由子问题的最优解组合而成。

一般解题步骤

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

二、Leetcode 455.分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是满足尽可能多的孩子，并输出这个最大数值。

示例：

python">输入: g = [1,2,3], s = [1,1]
输出: 1
解释: 
你有三个孩子和两块小饼干，3 个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是 1，你只能让胃口值是 1 的孩子满足。
所以你应该输出 1。

引用：

原文链接：https://programmercarl.com/0455.%E5%88%86%E5%8F%91%E9%A5%BC%E5%B9%B2.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
题目链接：https://leetcode.cn/problems/assign-cookies/description/
视频讲解：https://www.bilibili.com/video/BV1MM411b7cq/

为了满足更多的小孩，就不要造成饼干尺寸的浪费。

大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子，那么就应该优先满足胃口大的。

这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。

要更多的节省饼干，所以每个小孩分到的饼干够用就行。

先将两个数组进行排序，然后利用双指针算法，每个孩子选择最小且够吃的饼干。

代码：

python">class Solution:def findContentChildren(self, g: List[int], s: List[int]) -> int:count = 0s.sort()g.sort()i = 0j = 0while i<len(g) and j<len(s):if s[j] >= g[i]:j += 1i += 1count += 1else:j += 1return count

二、Leetcode 376. 摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

例如， [1, 7, 4, 9, 2, 5] 是一个摆动序列，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。

相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums ，返回 nums 中作为摆动序列的最长子序列的长度。

示例：

python">输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。

引用：

原文链接：https://programmercarl.com/0376.%E6%91%86%E5%8A%A8%E5%BA%8F%E5%88%97.html
题目链接：https://leetcode.cn/problems/wiggle-subsequence/description/
视频讲解：https://www.bilibili.com/video/BV17M411b7NS/

源自代码随想录

我们借用一下代码随想录给出的图片，这样就很好理解我们都需要做什么事情。

图中给出要删除非摆动的点，其实只是方便我们理解。我们在实际操作中并不需要去复杂的删除点，只需要记录一下摆动点的数量即可。

我们定义两个变量 preddiff==num[i]-nums[i-1] 和 curdiff=nums[i+1]-nums[i]，用来记录某个点左右的变化值，所以我们的终止条件就可以写为如下形式

python">if (prediff>0 and curdiff<0) or (prediff<0 and curdiff>0):result += 1

在此基础上，我们还有三个需要注意的细节。

上下坡中有平路
源自代码随想录
在这里最后一个 2，我们的 prediff 值等于零， curdiff 小于零，这种情况我们也算是一种摆动，所以我们也需要记录一下。我们就需要完善一下终止条件：

python">if (prediff>=0 and curdiff<0) or (prediff<=0 and curdiff>0):result += 1

首尾值
当数组只有两个值的时候，我们这种判断条件需要三个值，会发生 IndexError 。

我们可以在数组开头前面默认多加一个平路（并不是真正的去添加一个元素），并设置 prediff 的初始值就为零，这样上面的判断条件完全可以涵盖这种情况。

对于最后一个元素，根据题目描述它是一定会形成一个摆动的，所以我们在循环的时候就不遍历最后一个元素，并且设置初始结果的值为 1。

python">result = 1
prediff = 0
for i in range(len(nums)-1):pass

单调坡中有平路
源自代码随想录
由图中可以看出，第一个 2 和最后一个 2 都是符合我们记录摆动值的条件，最后摆动的结果是 3，但是我们实际的摆动结果是 2。

我们在记录 prediff 的值的时候并不是直接使用 nums[i]-nums[i-1] 进行赋值，而是不断的去跟踪 curdiff 的值。

我们只需要在这个坡度摆动变化的时候，更新 prediff 就行，这样 prediff 在单调区间有平坡的时候就不会发生变化，造成我们的误判。

代码：

python">class Solution:def wiggleMaxLength(self, nums: List[int]) -> int:result = 1prediff = 0curdiff = 0if len(nums) == 1:return resultfor i in range(len(nums)-1):curdiff = nums[i+1] - nums[i]if (prediff<=0 and curdiff>0) or (prediff>=0 and curdiff<0):result += 1prediff = curdiffreturn result

三、Leetcode 53. 最大子序和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例：

python">输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

引用：

原文链接：https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C.html
题目链接：https://leetcode.cn/problems/maximum-subarray/description/
视频讲解：https://www.bilibili.com/video/BV1aY4y1Z7ya/

暴力美学：使用两层 for 循环，外层遍历子数组的起始位置，内层循环来控制子数组的长度，最后将最大值的结果保存即可。暴力法的时间复杂度为 O(n^2)，超时。

贪心思想：这题的贪心思想在于，当我们的连续和为负数时，它对后续的和起到的是副作用（越加越小），所以我们直接抛弃这段子数组，从新的结点开始。

我们使用 result 保存最大连续和的时候，这个操作一定要在判断连续和是否小于零的前面，因为最大和也有可能是负数。

代码：

python">class Solution:def maxSubArray(self, nums):# 暴力法result = float('-inf')  # 初始化结果为负无穷大count = 0for i in range(len(nums)):  # 设置起始位置count = 0for j in range(i, len(nums)):  # 从起始位置i开始遍历寻找最大值count += nums[j]result = max(count, result)  # 更新最大值return result# 贪心算法result = float('-inf')count = 0for i in range(len(nums)):count += nums[i]result = max(count, result)if count <= 0:count = 0return result