[数据结构与算法]贪心的问题合集（Leetcode题解-Python语言）

贪心算法（Greedy Algorithm）：是一种在每次决策时采用当前状态下最优或最好的策略，从而希望导致结果是最好或最优的算法。

455. 分发饼干

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort(reverse=True)
        s.sort(reverse=True)
        p1, p2 = 0, 0
        ans = 0
        while p2 < len(s) and p1 < len(g):
            if s[p2] >= g[p1]:
                ans += 1
                p1 += 1
                p2 += 1
            else:
                p1 += 1
        return ans

思路不难，对饼干和孩子进行排序，由大到小，然后从最大的饼干和最大的孩子开始考虑：如果饼干能满足当前孩子，则计数加 1，考虑下一个饼干和孩子；如果不能满足，则考虑下一个孩子。直到孩子或者饼干考虑完为止。

860. 柠檬水找零

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

同样是分类讨论，如果收到 5 块则 5 块加 1，如果收到 10 块则找零 5 块（10块加1，5块减1），如果收到 20 块则优先使用 10 块 + 5 块找零，其次再考虑用 3 张 5 块找零，凡是无法找零都返回 False。

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

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        nums.sort()
        index = 0
        while index < len(nums) and k > 0 and nums[index] < 0:
            nums[index] = -nums[index]
            index += 1
            k -= 1
        if k > 0 and k % 2 != 0:
            return sum(nums) - 2 * min(nums)
        else:
            return sum(nums)

首先对数组排序，从小到大，然后取反先从负数开始（如果有的话），如果没有负数了，还剩余取反次数的话，就只考虑奇数的情况（偶数可以抵消），这时就对最小的正数（也是最小的数，因为没负数了）取反即可。

738. 单调递增的数字

class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        a = list(str(n))
        for i in range(len(a)-1,0,-1):
            if int(a[i]) < int(a[i-1]):
                a[i-1] = str(int(a[i-1]) - 1)
                a[i:] = '9' * (len(a) - i)  
        return int("".join(a)) 

考虑两个相邻数字的情况，如果左边的比右边大，则为了满足单调递增的条件，必定是左边的数减 1 而右边的数变成 9（因为要单调递增，所以右边所有数都变成 9）。从个位数（右边）向左开始考虑每一对数字的情况，当出现左边数减 1 时，右边的所有数字一定都变成 9。