贪心算法（Greedy）#

贪心算法是一种在每一步选择中都采取当前状态下最好或最优（即最有利）的选择，
希望通过局部最优解最终导出全局最优解。

🔸 考点梳理#

✅ 贪心选择性质：局部最优解能导出全局最优解。
✅ 最优子结构：问题的最优解可由子问题的最优解构成。
✅ 正确性证明方法：
- 数学归纳法
- 反证法
- 反例排除

455. 分发饼干#

LeetCode 455. Assign Cookies

1
class Solution:
2
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
3
        g.sort()
4
        s.sort()
5
        res = 0
6
        index = len(s) - 1
7
        for i in range(len(g) - 1, -1, -1):
8
            if index >= 0 and s[index] >= g[i]:
9
                res += 1
10
                index -= 1
11
        return res

376. 摆动序列#

LeetCode 376. Wiggle Subsequence

1
class Solution:
2
    def wiggleMaxLength(self, nums: List[int]) -> int:
3
        if len(nums) <= 1:
4
            return len(nums)
5
        pre_diff = 0
6
        cur_diff = 0
7
        res = 1  # 至少有一个元素
8
        for i in range(len(nums) - 1):
9
            cur_diff = nums[i + 1] - nums[i]
10
            if (pre_diff <= 0 and cur_diff > 0) or (pre_diff >= 0 and cur_diff < 0):
11
                res += 1
12
                pre_diff = cur_diff
13
        return res

53. 最大子数组和#

LeetCode 53. Maximum Subarray

1
class Solution:
2
    def maxSubArray(self, nums: List[int]) -> int:
3
        n = len(nums)
4
        if n == 0:
5
            return 0
6
        dp = [0] * n  # dp[i] 表示以 nums[i] 结尾的最大子数组和
7
        dp[0] = nums[0]
8
        res = nums[0]
9
        for i in range(1, n):
10
            dp[i] = max(nums[i], nums[i] + dp[i - 1])
11
            res = max(res, dp[i])
12
        return res