代码随想录训练营 Day27打卡 贪心算法 part01 理论基础 455. 分发饼干 376. 摆动序列 53. 最大子序和

代码随想录训练营 Day27打卡 贪心算法 part01

一、 理论基础

贪心算法的核心思想是：在解决问题时，通过在每个阶段都选择局部最优解，从而期望达到全局最优解。尽管这种方法并不总是有效，但在某些特定问题中，它能够非常高效地找到最优解。

举例说明

假设你面前有一堆钞票，你可以选择拿走其中的十张。如果你希望最终拿到的金额最大，那么每次都选择面值最大的钞票，这样最后你拿到的总金额就是最大的。这种每次选择当前最优解的策略，就是贪心算法的应用。

适用条件

贪心算法的关键在于判断局部最优解能否推导出全局最优解。然而，贪心算法并没有固定的套路，关键在于具体问题的分析和手动模拟。

解题步骤

尽管贪心算法没有固定的套路，但一般可以按以下步骤来尝试解决问题：

1. 分解问题： 将问题分解为若干个子问题。
2. 选择贪心策略： 找出一个适合的贪心策略，即如何在每个阶段选择局部最优解。
3. 求解子问题： 对每一个子问题，求解其最优解。
4. 构建全局最优解： 将所有子问题的局部最优解堆叠起来，形成问题的全局最优解。

二、 力扣455. 分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
示例 :
输入: g = [1,2,3], s = [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。

为了有效地分配饼干以满足尽可能多的小孩，并尽量减少浪费，我们可以采用一种贪心算法。这里的关键思想是利用饼干尺寸的最大效用，即用大尺寸的饼干去满足胃口较大的小孩，从而最大化满足小孩的数量。

局部最优：对于每个小孩，使用剩余饼干中最大的一块来满足他们的需求，这样可以充分利用大尺寸饼干的价值，即尽可能满足胃口大的小孩。

全局最优：通过这种方式，我们最终可以满足尽可能多的小孩，因为大尺寸的饼干不仅可以满足胃口大的小孩，还可以满足胃口较小的小孩。

如图所示：

版本一 贪心算法 大饼干优先

实现思路：

这个版本的思路是从最大的饼干和最大的孩子胃口开始匹配，确保尽量用大饼干去满足大胃口的孩子。
先对孩子的胃口和饼干的尺寸进行排序。
采用逆序遍历孩子的胃口数组，同时从饼干数组的最后一个元素开始逐个匹配。
如果饼干的尺寸能够满足当前孩子，则计数器增加，并继续寻找下一块饼干和下一个孩子。
这种方法可以有效地保证在满足大胃口孩子的同时，尽量满足更多的孩子。

class Solution:
    def findContentChildren(self, g, s):
        g.sort()  # 将孩子的贪心因子排序
        s.sort()  # 将饼干的尺寸排序
        index = len(s) - 1  # 饼干数组的下标，从最后一个饼干开始
        result = 0  # 满足孩子的数量
        for i in range(len(g)-1, -1, -1):  # 遍历孩子的胃口，从最后一个孩子开始
            if index >= 0 and s[index] >= g[i]:  # 如果当前饼干的尺寸大于等于当前孩子的胃口
                result += 1  # 满足当前孩子，结果计数器加一
                index -= 1  # 饼干下标左移一位，继续寻找下一块饼干
        return result  # 返回满足的孩子数目

1
2
3
4
5
6
7
8
9
10
11
12

版本二 贪心算法 小饼干优先

实现思路：

这个版本的思路是优先用小饼干去满足孩子，尽量让尽可能多的孩子得到满足。
先对孩子的胃口和饼干的尺寸进行排序。
从最小的饼干开始，遍历每一块饼干，同时从第一个孩子开始匹配。
如果饼干的尺寸能够满足当前孩子，则计数器增加，并继续匹配下一个孩子。
这种方法可以有效地利用较小的饼干来满足孩子，尽量使更多的孩子得到满足。

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

1
2
3
4
5
6
7
8
9
10

版本三 栈实现 大饼干优先

实现思路：
这个版本的思路同样是从大饼干开始，但是使用了双端队列（deque）来处理数据。
先对孩子的胃口和饼干的尺寸进行从大到小的排序，并将它们放入双端队列中。
通过双端队列的先进先出特性，从队列的队首取出最大值进行匹配。
如果当前的饼干能满足当前的孩子，则增加计数器。如果不能满足，则将饼干重新放回队首，继续匹配下一个孩子。
这种方法使用了队列来优化操作，有助于理解和处理类似问题。

from collections import deque

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        result = 0  # 满足孩子的数量
        queue_g = deque(sorted(g, reverse=True))  # 将孩子的贪心因子从大到小排序并转化为双端队列
        queue_s = deque(sorted(s, reverse=True))  # 将饼干的尺寸从大到小排序并转化为双端队列
        
        while queue_g and queue_s:  # 当孩子和饼干的队列都不为空时进行匹配
            child = queue_g.popleft()  # 取出孩子队列的队首元素（最大贪心因子）
            cookies = queue_s.popleft()  # 取出饼干队列的队首元素（最大尺寸）
            if child <= cookies:  # 如果当前饼干能够满足当前孩子
                result += 1  # 满足当前孩子，结果计数器加一
            else:
                queue_s.appendleft(cookies)  # 如果当前饼干不能满足孩子，则将饼干放回队首，继续匹配下一位孩子
        return result  # 返回满足的孩子数目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

力扣题目链接
题目文章讲解
题目视频讲解

三、 力扣376. 摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。
示例 ：
输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。

思路讲解

本题要求通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
来分析一下，要求删除元素使其达到最大摆动序列，应该删除什么元素呢？如图所示：

局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。

整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。

这是我们思考本题的一个大体思路，但本题要考虑三种情况：

情况一：上下坡中有平坡
情况二：数组首尾两端
情况三：单调坡中有平坡

情况一：上下坡中有平坡

例如 [1,2,2,2,1]这样的数组，如图：

可以统一规则，删除左边的三个 2：

情况二：数组首尾两端

题目中说了，如果只有两个不同的元素，那摆动序列也是 2。

例如序列[2,5]，如果靠统计差值来计算峰值个数就需要考虑数组最左面和最右面的特殊情况。
为了规则统一，针对序列[2,5]，可以假设为[2,2,5]，这样它就有坡度了即 preDiff = 0，如图：

情况三：单调坡度有平坡

在版本一中，我们忽略了一种情况，即 如果在一个单调坡度上有平坡，例如[1,2,2,2,3,4]，如图：

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

版本一 贪心法

这个版本的贪心算法通过比较相邻元素的差值，判断当前子序列是否形成一个波动（摆动）。
初始时，假设最右边的元素是一个波峰或波谷，因此结果从1开始。
通过遍历数组，比较当前元素与下一个元素的差值，若发现当前序列形成一个摆动，则将结果加1，并更新前一个差值。
最后返回结果，即为最长摆动子序列的长度。

class Solution:
    def wiggleMaxLength(self, nums):
        if len(nums) <= 1:
            return len(nums)  # 如果数组长度为0或1，则返回数组长度

        curDiff = 0  # 当前一对元素的差值
        preDiff = 0  # 前一对元素的差值
        result = 1  # 记录峰值的个数，初始为1（默认最右边的元素被视为峰值）

        for 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 += 1  # 峰值个数加1
                preDiff = curDiff  # 更新前一对元素的差值，只在摆动变化的时候更新

        return result  # 返回最长摆动子序列的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

版本二 贪心法二

与第一个贪心版本类似，此版本通过判断相邻元素差值的乘积来确定是否出现波动（摆动）。
当差值的乘积小于等于0且差值不为0时，说明当前序列形成了一个波动，此时结果加1，并更新前一个差值。
这种方法更加紧凑，使用条件判断来处理差值为0的情况，避免不必要的摆动计数。
最终返回的结果为最长摆动子序列的长度。

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        if len(nums) <= 1:
            return len(nums)  # 如果数组长度为0或1，则返回数组长度

        preDiff, curDiff, result = 0, 0, 1  # 初始化前一对元素差值、当前差值、以及结果

        for i in range(len(nums) - 1):
            curDiff = nums[i + 1] - nums[i]  # 计算当前元素与下一个元素的差值

            # 如果当前差值和前一差值的乘积小于等于0，并且当前差值不等于0，则意味着出现了摆动
            if curDiff * preDiff <= 0 and curDiff != 0:
                result += 1  # 峰值个数加1
                preDiff = curDiff  # 更新前一对元素的差值，确保下次比较时使用的是最新的差值

        return result  # 返回最长摆动子序列的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

版本三 动态规划

动态规划方法通过构建一个二维数组dp，记录每个元素作为波峰和波谷时的最长摆动子序列长度。
初始化时，每个元素作为波峰和波谷的长度都为1。
对于每个元素nums[i]，遍历其之前的所有元素nums[j]，根据大小关系判断nums[i]是否可以作为波峰或波谷，并更新对应的最大长度。
最终返回数组最后一个元素的波峰或波谷的最大值，表示最长摆动子序列的长度。

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        # dp数组用于存储每个元素作为波峰和波谷的最长摆动子序列长度
        dp = []

        for i in range(len(nums)):
            dp.append([1, 1])  # 初始化每个元素的波峰和波谷长度都为1

            for j in range(i):
                # 如果当前元素nums[i]小于之前的元素nums[j]，则它可以作为一个波谷
                if nums[j] > nums[i]:
                    dp[i][1] = max(dp[i][1], dp[j][0] + 1)  # 更新波谷的长度

                # 如果当前元素nums[i]大于之前的元素nums[j]，则它可以作为一个波峰
                if nums[j] < nums[i]:
                    dp[i][0] = max(dp[i][0], dp[j][1] + 1)  # 更新波峰的长度

        # 返回最后一个元素作为波峰或波谷的最大长度
        return max(dp[-1][0], dp[-1][1])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

力扣题目链接
题目文章讲解
题目视频讲解

四、 力扣53. 最大子序和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 ：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。

全局最优：选取最大“连续和”

局部最优的情况下，并记录最大的“连续和”，可以推出全局最优。

如动画所示：

这个算法使用了贪心的思想，通过一次遍历数组来找到最大子数组和。它的关键在于在遇到当前子数组和为负或零时，选择重新开始计算，而不是继续累加，从而确保了每一步都在寻找可能的最大值。该算法的时间复杂度为O(n)，空间复杂度为O(1)，非常高效。

代码实现

class Solution:
    def maxSubArray(self, nums):
        result = float('-inf')  # 初始化结果为负无穷大，确保任何输入数组都可以更新此值
        count = 0  # 用于记录当前子数组的累计和
        
        for i in range(len(nums)):
            count += nums[i]  # 累加当前元素到当前子数组的和
            
            if count > result:  # 如果当前子数组的和大于已知的最大值，则更新最大值
                result = count
            
            if count <= 0:  # 如果当前子数组的和小于等于0，说明这个子数组不可能对后续部分有正贡献
                count = 0  # 重置累计和，开始考虑下一个可能的子数组
            
        return result  # 返回最终的最大子数组和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

力扣题目链接
题目文章讲解
题目视频讲解