理论基础

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

刷题或者面试的时候，手动模拟一下感觉可以局部最优推出整体最优，而且想不到反例，那么就试一试贪心。

455. 分发饼干

link

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

对每个孩子 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: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        num = 0

        sp = len(s) - 1
        gp = len(g) - 1

        while sp >= 0 and gp >= 0:
            if s[sp] >= g[gp]:
                num += 1
                sp -= 1
                gp -= 1
            else:
                gp -= 1
        return num

1005.K次取反后最大化的数组和

link

给你一个整数数组 nums 和一个整数 k ，选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。重复这个过程恰好 k 次。可以多次选择同一个下标 i 。以这种方式修改数组后，返回数组可能的最大和。

示例：

输入：nums = [4,2,3], k = 1
输出：5
解释：选择下标 1 ，nums 变为 [4,-2,3] 。

思路

贪心思路：每次都选最小的值来反转（注意是在修改后的数组中找最小的），注意如果最小值为 0，则应该多次选 0。思路如下：

将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
从前向后遍历，遇到负数将其变为正数，同时K–
如果K还大于0，那么反复转变数值最小的元素，将K用完
求和

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        nums.sort(key=lambda x: abs(x), reverse=True)

        for i in range(len(nums)):  # 第二步：执行K次取反操作
            if nums[i] < 0 and k > 0:
                nums[i] *= -1
                k -= 1

        if k % 2 == 1:  # 第三步：如果K还有剩余次数，将绝对值最小的元素取反
            nums[-1] *= -1

        result = sum(nums)  # 第四步：计算数组A的元素和
        return result

注意 python 排序的写法。

sort 方法的 key 参数表示排序时，不直接用列表元素本身来比较，而是先对每个元素应用一次 key 函数，然后用返回值来排序。
lambda x: abs(x) 为一个匿名函数，表示接收一个参数 x，返回 x 的绝对值（abs(x)）。等价于：

1 2	def f(x): return abs(x)

所以也可以写成 nums.sort(key=f)

860.柠檬水找零

link

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。注意，一开始你手头没有任何零钱。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

示例：

输入：bills = [5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。

思路

每次找钱的时候都计算当前的钱是否满足，感觉这段代码有点暴力的思想？如果钱的组合更复杂怎么办？

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        money = Counter()
        
        for i in bills:
            if i == 5:
                money[5] += 1
            elif i == 10:
                if money[5] >= 1:
                    money[10] += 1
                    money[5] -= 1
                else:
                    return False
            else:
                if money[10] >= 1 and money[5] >= 1:
                    money[10] -= 1
                    money[5] -= 1
                elif money[5] >= 3:
                    money[5] -= 3
                else:
                    return False
        return True

正确理解：共有三种情况：

情况一：账单是 5，直接收下。
情况二：账单是 10，消耗一个 5，增加一个 10
情况三：账单是 20，优先消耗一个 10 和一个 5，如果不够，再消耗三个 5

情况三存在贪心思想，因为美元 10 只能给账单 20 找零，而美元 5 可以给账单 10 和账单 20 找零，美元 5 更万能。所以局部最优：遇到账单 20，优先消耗美元 10，完成本次找零。全局最优：完成全部账单的找零。