贪心算法：5 个实战案例（附 LeetCode 题解）

贪心算法在每一步选择中都采取当前状态下最优的决策，最终得到全局最优解。以下是 5 个经典案例，均附 Python 实现和 LeetCode 题解。

---

案例 1：分发饼干（LeetCode 455）

问题描述
给定孩子胃口值数组 $g$ 和饼干尺寸数组 $s$，每个孩子最多分得一块饼干。若 $s_j \geq g_i$，则饼干 $j$ 可满足孩子 $i$。求最多可满足的孩子数。

贪心策略

• 优先满足胃口最小的孩子
• 使用能满足该孩子的最小饼干
  数学表达：
  $$ \text{max} \sum_{i=1}^{n} \mathbf{1}_{s_j \geq g_i} \quad \text{s.t.} \quad j \text{ 未被使用} $$

def findContentChildren(g, s):
    g.sort()
    s.sort()
    child = cookie = 0
    while child < len(g) and cookie < len(s):
        if s[cookie] >= g[child]:
            child += 1
        cookie += 1
    return child

复杂度

• 时间：$O(n \log n + m \log m)$（排序开销）
• 空间：$O(1)$
  题解链接：LeetCode 455

---

案例 2：无重叠区间（LeetCode 435）

问题描述
给定区间数组 intervals = [[start_i, end_i]]，求最少移除多少区间可使剩余区间互不重叠。

贪心策略

• 按结束时间升序排序
• 优先保留结束早的区间，减少后续重叠
  数学表达：
  $$ \text{min} \left( n - \max_{\text{非重叠}} |S| \right) $$

def eraseOverlapIntervals(intervals):
    intervals.sort(key=lambda x: x[1])
    end = float('-inf')
    count = 0
    for s, e in intervals:
        if s >= end:
            end = e
        else:
            count += 1
    return count

复杂度

• 时间：$O(n \log n)$
• 空间：$O(1)$
  题解链接：LeetCode 435

---

案例 3：买卖股票 II（LeetCode 122）

问题描述
给定股价数组 prices，可多次买卖（卖后方可再买），求最大利润。

贪心策略

• 所有上涨日都买卖：若 $p_i > p_{i-1}$，则利润累加 $p_i - p_{i-1}$
  数学表达：
  $$ \text{profit} = \sum_{i=1}^{n} \max(p_i - p_{i-1}, 0) $$

def maxProfit(prices):
    profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i-1]:
            profit += prices[i] - prices[i-1]
    return profit

复杂度

• 时间：$O(n)$
• 空间：$O(1)$
  题解链接：LeetCode 122

---

案例 4：跳跃游戏（LeetCode 55）

问题描述
给定数组 nums，初始位置在索引 0，$nums_i$ 表示从 $i$ 可跳跃的最大长度。判断能否到达最后一个索引。

贪心策略

• 维护当前能到达的最远位置 max_reach
• 若 $i > \text{max_reach}$ 则失败
  数学表达：
  $$ \text{max_reach} = \max_{k \leq i} (k + \text{nums}_k) $$

def canJump(nums):
    max_reach = 0
    for i in range(len(nums)):
        if i > max_reach:
            return False
        max_reach = max(max_reach, i + nums[i])
    return True

复杂度

• 时间：$O(n)$
• 空间：$O(1)$
  题解链接：LeetCode 55

---

案例 5：划分字母区间（LeetCode 763）

问题描述
给定字符串 s，将其划分为尽可能多的片段，使得同一字母最多出现在一个片段中。

贪心策略

1. 记录每个字母最后出现的位置
2. 遍历时更新当前片段的边界 end = \max(\text{end}, \text{last}_c)
3. 当 $i = \text{end}$ 时分割片段

def partitionLabels(s):
    last = {c: i for i, c in enumerate(s)}
    start = end = 0
    res = []
    for i, c in enumerate(s):
        end = max(end, last[c])
        if i == end:
            res.append(end - start + 1)
            start = i + 1
    return res

复杂度

• 时间：$O(n)$
• 空间：$O(1)$（字母表大小固定）
  题解链接：LeetCode 763

---

贪心算法核心要点

1. 适用场景：问题具有最优子结构，且局部最优能导向全局最优
2. 证明关键：需证明贪心选择的安全性（如交换论证、数学归纳法）
3. 典型问题特征：区间调度、背包变种、路径覆盖、分配问题等

以上代码均通过对应 LeetCode 测试用例，可直接提交验证。